搜索回溯算法（DFS）1------递归

���录

简介：

递归问题解题的思路模板

例题1：汉诺塔

例题2：合并两个有序链表

例题3：反转链表

例题4：两两交换链表中的节点

例题5：Pow（x,n）-快速幂

结语：

---

简介：

本系列将会带大家深入理解搜索中的一大分支深搜，深搜是离不开递归的和回溯思想的（优化需要剪枝），故我会在例题中详细指出解决这一系列问题的思考思路和解题技巧。

那么我们就从递归开始（深搜的基础）也就是本文中主要介绍的。

什么是递归？

简单来说就是函数自己调用自己。

为什么会用到递归？

大问题可以拆解成相同的子问题，且子问题的解法和大问题的一模一样，这是就可以用到递归。

在解决⼀个规模为n的问题时，如果满⾜以下条件，我们可以使用递归来解决：

a. 问题可以被划分为规模更⼩的⼦问题，并且这些⼦问题具有与原问题相同的解决⽅法。

b. 当我们知道规模更⼩的⼦问题（规模为n-1）的解时，我们可以直接计算出规模为n的问题的解。

c. 存在⼀种简单情况，或者说当问题的规模⾜够⼩时，我们可以直接求解问题。

⼀般的递归求解过程如下：

a. 验证是否满⾜简单情况。

b. 假设较⼩规模的问题已经解决，解决当前问题。

上述步骤可以通过数学归纳法来证明。

如何理解递归？

不要太在意细节，相信函数。 

递归问题解题的思路模板

当然在设计递归函数之前最重要的是你要你的递归函数干嘛。

1.递归函数的作用

2.相同子问题------------函数头

3.只关心某一个子问题是如何解决的------------函数体

4.递归出口

建议友友在写递归类型的题目是一定要把这三个地方考虑清楚了再下手。

最后就是相信函数。

例题1：汉诺塔

链接：汉诺塔

题目简介：

递归问题非常经典的一道题目，在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:

(1) 每次只能移动一个盘子;

(2) 盘子只能从柱子顶端滑出移到下一根柱子;

(3) 盘子只能叠在比它大的盘子上。

请编写程序，用栈将所有盘子从第一根柱子移到最后一根柱子。

解法：

我们可以看到每次都可以把大问题分解成相同的子问题，且子问题的解决方法和大问题的一模一样故我们可以使用递归来处理。 

1.递归函数的作用

函数作⽤：将A中的上⾯n个盘⼦挪到C中。这里的A和C是函数参数的A和C不是实际的（很重要）。

2.相同子问题（函数头）

我们要设计一个函数头来完成汉诺塔的递归过程，我们可以看到我们需要三根柱子和要记录下来还剩下几个盘子。故我们的函数头可以设计成public void dfs(List a, List b, List c, int n)。关于List如果友友还没有学到的话可以把他看成一个数组。

3.只关心某一个子问题是如何解决的（函数体）

我们取第三层汉诺塔来研究（大问题被拆成3层汉诺塔）。

我们发现子问题刚来三件事

1.把A上面n - 1 个盘子通过C移动到B 

2.把A上面最后一个盘中移动到C

3.把B上面n - 1个盘中通过A 移动到C

dfs(a, c, b, n - 1);

c.add(a.remove(a.size() - 1));//这里是因为给出的例题这样做就是把盘中从A移动到C（理解思路即可）

dfs(b, a, c, n - 1);

4.递归出口

当问题的规模变为n=1时，即只有⼀个盘⼦时，我们可以直接将其从A柱移动到C柱。

本例题代码实现如下：

class Solution {    public void hanota(List A, List B, List C) {        dfs(A,B,C,A.size());    }    public void dfs(List A, List B, List C,int n ){        if(n == 1){            C.add(A.remove(A.size() - 1));            return;        }        dfs(A,C,B,n - 1);        C.add(A.remove(A.size() - 1));        dfs(B,A,C,n - 1);    }}

关于本例题要注意的点：c.add(a.remove(a.size() - 1));可能有的友友会纠结为什么不是remove（0）呢，其实自己模拟一下即可，我们移走盘子是从最上面那个盘子开始移动的。

不用太深究函数的细节（陷入将无法自拔），如果是第一次的话可以去b站上看看递归的全过程细节（这里的不用深究是建立在已经对它的展开有一定理解了，第一次学汉诺塔的话我还是建议大家可以看看别人推的整个过程，理解更加深刻）。

例题2：合并两个有序链表

链接：合并两个有序链表

题目简介：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

解法：

通过分析题目我们发现可以把大问题拆成下图的子问题，上面的1已经合并有序现在要让2，4和下面链表合并有序。

故我们可以用递归来解决这道问题。

1.递归函数的作用

交给你两个链表的头结点，你帮我把它们合并起来，并且返回合并后的头结点.

2.相同子问题（函数头）

由上图可以看到函数要包含两个链表还要能返回合并后的链表故函数头设定为：public ListNode mergeTwoLists(ListNode l1, ListNode l2)

3.只关心某一个子问题是如何解决的（函数体）

选择两个头结点中较小的结点作为最终合并后的头结点，然后将剩下的链表交给递归函数去处理。

4.递归出口

当某⼀个链表为空的时候，返回另外⼀个链表。

代码如下：

class Solution {    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {        if(list1 == null){            return list2;        }        if(list2 == null){            return list1;        }        if(list1.val