数据结构与算法|【递归，搜索与回溯算法 & 递归算法】递归算法入门详解：递归算法小专题

汉诺塔问题

题目解析

什么是汉诺塔问题

通过三根柱子，把最左边柱子上的圆环移动到最右边；
每次只能移动一个圆环；
小圆环必须在大圆环之上；

汉诺塔问题的简单过程模拟

算法原理

为什么汉诺塔问题可以使用递归来解决呢？(Why?)

1. 如何解决汉诺塔问题？

要想知道为什么能使用递归来解决汉诺塔问题，我们先来解决：如何解决汉诺塔问题?

总结规律

解决两层汉诺塔的基本流程

对于2层汉诺塔的解决步骤：

解决三层汉诺塔的基本流程

对于3层汉诺塔的解决步骤：

所以，当胖子有 n 个时，先把底下最大的盘子移动到 poleC 上，那么就需要把上面 n-1 个盘子移动到 poleB 上；那当盘子有 n-1 个，也是同样的操作；

规律

当 N=n 时，我们只需要把第 n 个盘子先移动到 poleC 即可，此时就需要把 n -1 个盘子先移动到辅助杆 poleB 上，那么这 n-1 个盘子怎么移动呢？

在 N=n-1 的时候，我们已经解决过这个问题了，直接拿来用即可；

解法：递归 (How?)

重复子问题（函数头）

对于上图列出的情况，无论 N 等于多少，都要重复上面的 1，2，3 步：

重复子问题就是把某一根柱子x上的盘子，借助某一根柱子y，放到另一个柱子z上：

设置函数头：

void dfs( poleX , poleY, poleZ, 盘子数量) ；

作用：

给 dfs()传入三个柱子和盘子的数量，dfs()就可以把 x 上的 N 个盘子，借助 y 的帮助，传入到 z 上；

设置函数体

设计函数体，只需要关心某一个子问题在做什么，也就是 N 为某一个值时，盘子的移动流程；

第一步：借助 z 柱子，把 x 上的 n-1 个盘子移动到 y 上

函数体的第一步： dfs( x , z , y , n-1)

第二步：把 x 底下最大的盘子，从 x 移动到 z ：

函数体的第二步：x.back()，这个方法的作用是，把 x 最底下的盘子移动到 z 上；

第三步：把 y 上的 n-1 个盘子，借助 x 移动到 z 上：

函数体的第三步 dfs( y, x, z, n-1)；

递归出口

我们发现，当 N=1 时的处理过程，和 N>1 的处理过程完全不一样：

当 N=1，就不需要借助辅助柱子，直接移动即可；

所以N=1时处理盘子的方法，就是汉诺塔问题的递归出口； x.back()；

编写代码

方法一：递归

递归细节展开图

方法二：不讲武德

如果是笔试题，可以直接这样 ac，因为：

但是如果是面试题这样写，就回家等通知吧哈哈哈！！！

合并两个有序链表

题目解析

算法原理

解法：递归

（1）寻找重复子问题 (设计函数头)

我们定义两个指针 left1，left2，返回两个链表合并后的有序链表的头指针

因为这两个指针都是升序的，在刚开始遍历链表时，比较两条链表头节点，以较小节点作为最终合并链表后，返回的头节点；

接下来，就比较剩下的两条链表，找到两个新头节点中较小的节点，作为接下来新链表的下一个节点；

所以重复的子问题：是合并链表，返回新链表的下一个节点；

所以函数头为 Node dfs(Node l1, Node l2)，就是合并完链表，返回每次合并链表的末尾节点；

（2）某一个子问题的具体流程 (函数体)

第一步，比较大小；假设较小值为 l1；

第二步，让较小节点连接两条链表剩余部分合并后的结果即可；l1.next = dfs(l1.next , l2)；

返回合并链表的新加入节点 return l1；(假设 l1 ，l2 两个指针，l1指向较小的节点)

（3）递归出口

什么时候子问题不能再细分了呢？当两个指针其中一个指向对应链表的尾节点，就可以停止递归，返回另一个指针即可；此时另一条链表的剩余部分，会和合并链表的尾节点连接；

（4）编写代码

注意：无论当前节点是子问题还是递归出口，在拼接好剩余链表的合并部分后，都要返回当前节点;

拓展

(1) 递归问题和循环问题可以互相转换

递归和循环都是方法处理一个子问题，两者可以通过修改互相转换

(2) 使用递归&循环的时机

而如果通过递归解决的问题，要通过循环来解决，我们就需要借助栈，因为在递归时的一个代码块方法，在递归后该方法节点并没有完全执行完，等下层节点回溯之后，还会继续执行方法剩余部分；

但是如果使用循环，我们就需要使用栈来保存方法节点未执行完的信息，如果是解决汉诺塔问题，递归代码会非常简洁，而使用循环，那么代码成本就会大幅度提高；

但是如果递归展开图不是树形结构，那么把递归修改成循环也是比较容易的（不绝对），如遍历数组；对于使用递归遍历数组，子问题就是，给一个数组元素，把剩余的数组元素打印出来；

所以对于大多数情况下，如果递归图越复杂，越适合使用递归，反之则适合使用循环；

(3) 修改递归顺序可以改变遍历顺序

我们修改这两条代码的先后顺序，虽然递归图相同，但是遍历数组的顺序会被修改；

(4) 通过打印日志调试

反转链表

题目解析

算法原理

视角一：从宏观角度看待问题

我们可以先让 head.next.next = head：

再让 head.next = null 即可翻转前两个节点：

但是此时会出现一个问题，就是第三个节点丢失了；如果先修改，会出现丢失节点信息的情况；

既然先修改前面的节点指向会出现节点信息丢失，我们就调整修改顺序：

算法思路:

递归函数的含义: 交给你一个链表的头指针，你帮我逆序之后，返回逆序后的头结点;(想到递归函数的含义是这道题中最难的)
函数体: 先把当前结点之后的链表逆序，逆序完之后，把当前结点添加到逆序后的链表后面即可;
递归出口: 当前结点为空或者当前只有一个结点的时候，不用逆序，直接返回。