递归思路
首先我们要分析主问题，如果主问题可以拆分成一个又一个小问题的时候，并且这些小问题的解决方案也是一样的话，我们可以使用递归来解决。
递归函数头的设计是根据子问题的解决需要而设计的
函数体部分则是由如何解决子问题组成
最后就是递归的出口，其实就是分到不能再分的情况。
这里我们不要进行递归展开图的绘制，要相信我们的函数可以完成任务，就像相信你的编译器能进行代码的编译。
下面我们来实战演示一下：
实战演练
汉诺塔
https://leetcode.cn/problems/hanota-lcci/description/
太经典的题目了，这里就直接分析了，不解析题意了。
我们抽象一下，假设我们有 N 个盘子，我们需要先将 N - 1 个盘子借助 C 柱子 移动到 B 柱上，然后将 A 柱 上 的最后一个盘子直接移动到 C 柱上，最后我们将 B 柱 上的 N - 1 个盘子借助 A 柱 移动到 C 柱上
那么我们的递归函数头的设计应该是盘子数量 ， 三个柱子（初始位置，助力位置，目标位置）
递归的出口就是不能继续划分的情况也就是只有一个盘子的情况。
合并两java基础教程递归个链表
https://leetcode.cn/problems/merge-two-sorted-lists/description/
这道题我们可以采用递归的思路来写，首先找到子问题：
当我们遇到两条链表的时候，我们会选取其中一个 value 值较小的作为新链表的下一个连接结点，你会发现，每次遇到两条非空链表，都是重复上面的操作，所以函数头的参数也就是两条链表。
接着就是函数体的书写，首先需要比较，然后我们思考这个函数是做什么的？很显然，这个函数需要返回一个结点，这个结点需要连接到上一个递归函数的结点后面，所以这个函数应该是返回两个链表的合适的结点。
递归的出口，当其中一条链表为空的时候，返回另一条链表即可。
反转链表
https://leetcode.cn/problems/reverse-linked-list/description/
递归的函数的作用：反转链表，返回新的头节点
函数头的设计：需要一个链表参数
函数体设计：当我们使用递归函数会得到类似下图的链表：
当我们得到新的头节点时，我们需要将head.next 这个结点的 next 区域的指向修改为 head, 然后我们还需要将 head 的 next 域修改为 null，为什么需要这个操作，因为最后一个结点的时候，例如上面的 1 号结点，它的next 域指向为空，为了操作的统一，所以这里统一处理为 head.next = null
递归的出口，当 head 为空或者 head 后面没有结点，这时候无需反转链表，直接返回即可。
两两交换链表中的节点
https://leetcode.cn/problems/swap-nodes-in-pairs/description/
函数作用：返回一个交换过的链表的头节点，函数头需要一个参数也就是链表的头节点
函数体的设计：
head.next = 递归函数返回的头节点
r2.next = head
递归的出口：当头节点为空，或者头节点后面没有节点的时候，直接返回头节点即可
快速幂
https://leetcode.cn/problems/powx-n/
快速幂的方法：假设求 100 的 10 次方：
先求出一半的次方的幂，然后进行自我相乘，如果次方为奇数，则需要再乘 一个 x
那么这个递归函数的作用就是来求出快速幂的，传参有两个， x 和 n
在进行递归之前，我们先处理一下如果次方是负数的情况，需要进行转换，由于负数最小为 2 ^ -31 ，所以转化成（int 类型）的正数的时候，会发生溢出，这里就整型提升一下。
递归的出口：n == 0 ，返回1 ，n == 1 返回 自身。
递归与循环，搜索，回溯，剪枝的关系
递归和循环都是在重复做一件事情，所以递归和循环是可以相互转换的，当然有时候题目使用递归会好写代码，而有些题目使用循环会好写，这是因为我们递归如果是单分支的树，使用循环会更好，但是如果递归是二叉甚至 N 叉树的时候，使用循环就需要借助栈，，这时候循环就很难写了。
我们来看一下搜索，搜索分为广度优先遍历和深度优先遍历，学过图的老铁们应该很清楚，而我们的递归则是和深度优先遍历一样（简称深搜），所以搜索本质上也是递归，没有很神秘。
回溯，这个大家应该有听过回溯算法，实际还是和递归 / 搜索一样，回溯在递归里的表现就是递归到了底，然后向上回去，回去就是回溯。
剪枝可以说是递归 / 搜索 / 回溯的一个优化，就是你发现有些递归是不需要做的，就不进去递归，简单来看就是一个树有很多的岔路，当你知道有一条岔路绝对不可能是答案的时候，这时候使用剪枝就可以去掉这些没有的树枝，在代码理解来看就是不去这个递归。
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/25511.html