递归算是简单而又常见的算法，但是大多时候我们也只是能看懂他，而想要掌握他还是需要一定的技巧

递归的三大要素

第一要素：函数实现功能

对于一个函数，最先清楚的应该它说要实现的功能，也就是它要干什么，这个完全由函数定义者决定，所以，我们不应该最先思考里面代码怎么写，而是应该先思考，你这个函数用来写什么。递归也是一个函数，所以需要遵循这个规则。

例如，我们定义一个函数：

1
2
3
4
// 求1～n的和
func sum(n int) int{

}

这个函数的功能就是求1～n的和，到此，我们完成了函数的定义，也明确它实现的功能。

第二要素：寻找递归结束条件

递归就是在函数内部不断的调用这个函数本身，因此我们必须找出递归结束条件，否则，这个函数就会一直执行下去，成为一个死循环。找到结束条件，递归结束，并返回结果。根据这个结束条件，我们是可以直接知道函数的结果的。比如上面的例子，当n = 0时，你可以明确知道sum(n)的结果是什么，此时，sum(0) = 0。将第二要素添加到代码中，如下：

1
2
3
4
5
6
// 求1～n的和
func sum(n int) int{
    if n == 0 {
    	return n
    }
}

仔细思考，发现n = 1时，也可以直接得到结果，所以我们将他们合并，如下：

1
2
3
4
5
6
// 求1～n的和
func sum(n int) int{
    if n < 2 {
    	return n
    }
}

递归条件的定义必须要足够严谨，否则就会出现漏算或者多算的情况。

第三要素：找出函数的等价关系式

第三元素是需要不断缩小参数的范围，缩小后，可以通过一些辅助变量或操作使得原函数的结果不变。

上面的例子中，sum(n)范围比较大的时候，我们可以让sum(n) = n+sum(n-1)，这样范围就从n变成了n-1，以此类推，最终范围会缩小至我们第二要素的递归结束条件，并且原函数的结果不会变。

我们最终需要找到一个与原函数等价的关系式即可，sum(n)的等价关系式为n + sum(n-1)，即sum(n) = n + sum(n-1)

这个等价关系式的寻找，是整个递归中最难也是最重要的一部分，暂时不懂没有关系，多找一些递归相关的题，多练习熟悉之后自然就手到擒来了

找出了等价关系，将它添加到函数中完善函数，完整函数如下：

1
2
3
4
5
6
7
// 求1～n的和
func sum(n int) int {
	if n < 2 {
		return n
	}
	return n + sum(n-1)
}

至此递归三要素就全部写到函数中了，这个求和函数也完成了，每次做递归时试着将这三要素找出来，你就会觉得递归变得很简单。

还是不懂没关系，下面我们结合案例讲解一些题目。

案例

LeetCode 509.斐波拉切数

斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给你 n ，请计算 F(n) 。

结合上面的说讲的，是从三大要素入手

第一要素：定义函数

定义函数完成该功能

1
2
3
4
// 斐波拉契数列
func fib(n int) int {

}
第二要素：结束条件

通过观察可得，当n = 1或n = 2时，我们可以轻易知道结果fib(1) = fib(2) = 1，所以递归结束条件可以为n <=2 

1
2
3
4
5
6
// 斐波拉契数列
func fib(n int) int {
    if n <= 2{
        return 1
    }
}
第三要素：等价关系式

题目中已经给出了等价关系f(n) = f(n-1)+f(n-2) 。大多时候我们都是需要自己去寻找等下关系式，这也是最难的一个环节，因为题目中直接给出关系式的原因，所以直接写到函数中即可。

1
2
3
4
5
6
func fib(n int) int {
   if n <= 2 {
      return 1
   }
   return fib(n-1) + fib(n-2)
}

简单吧，一道非常简单且经典的求斐波拉契数列就完成了。

兔子跳台阶

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

第一要素：定义函数

定义函数完成该功能

1
2
3
4
// 兔子跳台阶
func jump(n int) int {

}
第二要素：结束条件

第二要素要找到可以最直观知道结果的jump(n)，当台阶数为1时我们可以很直观的知道，小兔子只有1种跳法；当台阶数为2时，小兔子也只有两种，再往上就不符合最直观的逻辑了，所以我们得出结束条件

1
2
3
4
5
6
// 兔子跳台阶
func jump(n int) int {
    if n <= 2 {
        return n
    }
}
第三要素：等价关系式

每次跳可跳一个或两个台阶，所以每次跳的时候又两种跳法：

  • 此次我跳了1个台阶，那么还剩下n-1个台阶没跳，所以剩下的台阶有jump(n-1)种跳法
  • 此次我跳了2个台阶，那么还剩下n-2个台阶没跳，所以剩下的台阶有jump(n-2)种跳法

所以兔子的全部跳法为两种跳法之和，jump(n) = jump(n-1)+jump(n-2)，熟悉吗，其实这就是一个斐波拉契数列。至此，等价关系式也就出来了

1
2
3
4
5
6
7
// 兔子跳台阶
func jump(n int) int {
   if n <= 2 {
      return n
   }
   return jump(n-1) + jump(n-2)
}

简单吧，下面来一个稍微复杂一点的

汉诺塔

从左到右有A、B、C三根柱子，其中A柱子上面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子上去，期间只有一个原则：一次只能移到一个盘子且大盘子不能在小盘子上面，求移动的步骤和移动的次数

img

第一要素：定义函数

定义函数完成该功能

1
2
3
4
// 汉洛塔
func hanota(n int, A, B, C string) {

}

再定义一个函数来打印移动

1
2
3
4
5
// 打印移动情况
func move(n int, original, target string) {
   m++
   fmt.Printf("第%d次移动， 把%d号盘子从%s移动到%s\n", m, n, original, target)
}
第二要素：结束条件

当我们只有一个圆盘的时候，直接把圆盘从A移到C即可

1
2
3
4
5
6
7
// 汉洛塔
func hanota(n int, A, B, C string) {
   if n == 1 {
      move(n, A, C)
      return
   }
}

第三要素：等价关系式

假设我们只有两个圆盘时，正确的移动步骤应该是：

  1. 将第一个圆盘，从A移到B
  2. 将第二个圆盘，从A移动C
  3. 将第一个圆盘，从B移到C

此时回到我们有N个圆盘的时候，我们将[1, n-1]个圆盘看作一个圆盘，这样我们就可以以两个圆盘的移动方式对待：

  1. 将[1, n-1]圆盘，从A移到B
  2. 将第n个圆盘，从A移动C
  3. 将[1, n-1]圆盘，从B移到C

此时等价关系式就出现了，hanota(n-1, A, C, B)与hanota(n-1, B, A, C)；不同于斐波拉契数列，他的关系式不需要返回，且有两个，但是大同小异，只是稍加变化而已。写进函数如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 汉洛塔
func hanota(n int, A, B, C string) {
   if n == 1 {
      move(n, A, C)
      return
   }
   // [1，n-1] 从A移到B
   hanota(n-1, A, C, B)
   // n 从A移到C
   move(n, A, C)
   // [1，n-1] 从B移到C
   hanota(n-1, B, A, C)
}

第三道题更前两道似乎不太一样，没有求和，也没有返回，但这确实也是递归，多假练习加以熟悉即可。

递归优化

因为递归是不断的去通过子函数实现最终的功能，如果不进行子函数的优化，就会导致重复计算，我们以上述斐波拉契数列为例

image-20210915230414278

求f(8)的过程，从上图可知，出现了3次f(5)，4次f(4)。。。。当n越大，里面出现的重复计算也就越多，优化还是很有必要的。

将这些可能重复的计算值存储起来，如果已经计算过直接返回即可，就无需重复计算，以此节省很多空间，优化后代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
// 斐波拉契数列
var mapFib = make(map[int]int)
func fib(n int) int {
   if n <= 2 {
      return 1
   }
   if v,ok := mapFib[n]; ok {
      return v
   }
   mapFib[n] = fib(n-1) + fib(n-2)
   return mapFib[n]
}