【算法详解】如何使用递归，递归使用的技巧详解

什么是递归

先来看下百度百科的定义：

程序调用自身的编程技巧称为递归（ recursion）。递归作为一种算法在程序设计语言中广泛应用。一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。一般来说，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进；当边界条件满足时，递归返回。

简单总结下来递归需要满足下面三个条件

1、一个问题可以分解为几个问题的解；

什么是子问题呢？就是数据规模更小的问题。

2、该问题分解之后的子问题，除了数据规模不同，求解思路完全一样；

3、存在递归终止条件。

拆解子问题的时候，我们会把问题拆分成子问题，然后在把子问题拆分成子子问题的过程，依次类推，这就需要一定有个终止条件，不能出现无限循环的错误情况出现。

什么问题适合使用递归解决？

一个问题可以被拆分成一个个的小问题，并且拆分之后问题能够变得更加简单，同时被一直拆分的问题也有一个明确的终点，这时候就可以考虑使用递归了。

编写递归的技巧

关键的技巧主要是

1、找出递推公式，就是如何将大问题拆分成小问题的规律；

2、因为有子问题的拆分循环，需要找出终止退出的条件；

3、还有一个比较关键的点，因为递归涉及到的层级很深，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤，基于现有的条件找出递推的公式。

面对递归，我们总是想弄明白每一步的调用逻辑，总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样很容易就会被设个问题绕进去了。

递归的缺点

递归调用，占用空间大；

递归太深，容易发生堆栈溢出；

可能存在重复计算。

来几个栗子

来几个递归算法的经典栗子，来了加深下对递归算法的了解

1、斐波那契数列

斐波那契数列是递归中一道非常经典的题目

斐波那契数列是指这样一些列数列：：1、1、2、3、5、8、13、21、…… 这个数列的规律就是从第三项开始的每一项都等于前面两项的和，例如 3+5=8，,5+8=13。

题目要求：输入序号 N，输出对应的斐波那契数？

用函数表示就是F(1)=1，F(2)=1，F(n)=F(n-1)+F(n-2)。

下面使用递归实现下

func f(n int) int {
	if n < 3 {
		return 1
	}

	return f(n-1) + f(n-2)
}

其中 F(n)=F(n-1)+F(n-2) 就是这道题目的递推公式

if n < 3 {
	return 1
}

就是终止退出的条件。

上面就是当传入的数据为 5，函数的递归调用过程

2、兔子繁衍问题

假设一对刚出生的小兔一个月后就能长成大兔，再过一个月就能生下一对小兔，并且此后每个月都生一对小兔，一年内没有发生死亡，问：一对刚出生的兔子，一年内繁殖成多少对兔子?

这也是一道经典的斐波那契数列问题，首先来分析下这个兔子的数据

通过分析可知，这就是典型的斐波那契数列问题 1、1、2、3、5、8、13、21

func f(n int) int {
	if n < 3 {
		return 1
	}

	return f(n-1) + f(n-2)
}

3、青蛙跳台阶问题

地址:https://leetcode.cn/problems/qing-wa-tiao-tai-jie-wen-ti-lcof/

一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2

示例 2：

输入：n = 7
输出：21

示例 3：

输入：n = 0
输出：1

解题思路：

首先找到递推公式，因为每次能够走 1 步或者 2 步。

所以n个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法加上先走 2 阶后，n-2 个台阶的走法。用公式表示就是：f(n)=f(n-1)+f(n-2)

再来看下终止条件

f(1) = 1
f(2) = 2

同时最终递归的数字肯定是落到 1 和 2 上了，那就可以设置最后的 1 和 2 为最终终止的条件

func f(n int) int {
	if n < 1 {
		return 1
	}
	if n < 2 {
		return 2
	}

	return f(n-1) + f(n-2)
}

4、汉诺塔问题

汉诺塔问题的描述：

假设有 A、B、C 三根柱子。其中在 A 柱子上，从下往上有 N 个从大到小叠放的盘子。我们的目标是，希望用尽可能少的移动次数，把所有的盘子由 A 柱移动到 C 柱。过程中，每次只能移动一个盘子，且在任何时候，大盘子都不可以在小盘子上面。

解题思路：

我们使用递归的思路去思考，首先找出递推的公式

我们把一个 N 层汉诺塔从 A 搬到 C，我们假定只有两层，首先把 N-1 层搬到 B,然后把下面的第 N 层搬到 C，然后再把 N-1 层从 B 搬到 C 。

如果存在多层，那我们就假定 N-1 层已经排好序了，只搬第 N 层，这样依次递归下去。

终止条件：

当只剩下最后一个的时候，我们只需要搬动一次就行了

var count int = 0

func main() {
	beadNum := 5 // This is the initial number of beads
	hanoi(beadNum, "A", "B", "C")
	fmt.Println(count)
}

func hanoi(beadNum int, pillarA string, pillarB string, pillarC string) {
	if beadNum == 1 {
		// 最后一个了，可以结束了
		move(beadNum, pillarA, pillarC)
	} else {
		// Step 2: 将 N-1 层从 A 移动到 B
		hanoi(beadNum-1, pillarA, pillarC, pillarB)
		// Step 2: 将第 N 层从 A 移动到 C
		move(beadNum, pillarA, pillarC)
		// Step 3: 将 B 中的 N-1 层移动到 C
		hanoi(beadNum-1, pillarB, pillarA, pillarC)
	}
}

func move(beadNum int, pillarFrom string, pillarTo string) {
	count += 1
}

5、二叉树的遍历

这里使用递归来实现下，二叉树的前序，中序，和后续的遍历

前序遍历

前序的就是先当前节点，然后左节点，然后右节点，这就是一层的递归

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func preorderTraversal(root *TreeNode) []int {
	var res []int
	if root != nil {
		res = append(res, root.Val)
		res = append(res, preorderTraversal(root.Left)...)
		res = append(res, preorderTraversal(root.Right)...)
	}

	return res
}

中序遍历

中序遍历的顺序为：先遍历左节点，然后遍历根节点，最后遍历右节点

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func inorderTraversal(root *TreeNode) []int {
	var res []int
	if root != nil {
		res = append(res, inorderTraversal(root.Left)...)
		res = append(res, root.Val)
		res = append(res, inorderTraversal(root.Right)...)
	}

	return res
}

后序遍历

后序遍历的顺序为：先遍历左节点，然后遍历右节点，最后遍历根节点

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func recursionPostorderTraversal(root *TreeNode) []int {
	var res []int
	if root != nil {
		res = append(res, recursionPostorderTraversal(root.Left)...)
		res = append(res, recursionPostorderTraversal(root.Right)...)
		res = append(res, root.Val)
	}

	return res
}