数据结构与算法系列之递归（GO）

以下完整代码均可从这里获取

https://github.com/Rain-Life/data-struct-by-go/tree/master/recursion/step



理解递归

已经不知道是第几次被递归阻断我学习数据结构的道路了，每次学到递归，我都自我怀疑，是我脑子有问题吗？我是真的学不明白它！



发现之前理解递归过于刻板和传统，看递归的时候总是按照机器的执行顺序一直的往每一层递归里边进，不断的下一层、下一层、下一层，直到自己彻底崩溃，自己的CPU也没把一个完整的递归给走完



我们的脑子总是想着跟着机器的执行，不停的往每一层里边进。其实完全可以不用关心每一层，只要假定下一层能够正确的返回，然后该怎么走就怎么走，保证最深的一层递归逻辑正确就行，也就是递归终止的条件



因为不管是递归的哪一层，他们执行的都是一样的代码，唯一不一样的只是数据而已，保证了递归的逻辑是正确的，每一层的的结果就是正确的，直到递归的终止条件被满足，然后每一层都会得到正确的结果



下边进入主题



递归应用十分广泛，可以说，如果没法完全的理解递归的思想，后边的一些进阶的数据结构根本没法学，或者非常吃力。比如深度优先搜索、二叉树的遍历等等



基本上大多数的关于数据结构的书，在介绍递归的时候都是拿斐波那契数列来举例的，其实我个人觉得虽然题目经典，但对我了解递归帮助不是很大，下边分享一个生活中的示例帮助理解递归



假设你现在在爬山，已经爬到了山腰上，假设你现在想知道自己在第多少级台阶上应该怎么办



此时递归就派上用场了，那如果你知道你前边一级的台阶是第多少级就行了，知道了它是第多少级，在它的级数上加一就知道你所在的位置是第几级台阶了。但是你前边的这一级也不知道是第几级，毕竟离山底有点远，没法知道。那就继续的往前推，前一级的前一级台阶是第几级台阶，直到第一级台阶，然后就可以一级一级的把数字传回来，直到你的前一级台阶告诉你他在第几级，你就知道了自己在第几级了



整个过程就是一个递归的过程，往前推的过程是”递“，回传的时候就是”归“。所有的递归问题都是可以用递归来表示的，对于上边的例子，用公式来表示就是

f(n) = f(n-1) + 1，其中f(1)=1



f(n)是你想自己自己在哪一级，f(n-1)就是你的前一级台阶是第几级，f(1)表示第一级台阶我们知道它是第一级。有了公式写递归代码就很轻松了

func Recursion(int n) int {
    if n==1 {
        return 1
    }
    
    return f(n-1) + 1
}



什么情况下适合使用递归



只要一个问题可以满足下边三个条件，那就可以考虑使用递归



一个问题的解可以分解成几个子问题的解

子问题就是规模更小的问题，比如前边的求自己在哪一级台阶的问题，可以分解成”前边一级是哪一级“这样的子问题



子问题除了数据规模不一样，求解思路必须完全一样

还是以上边的例子为例，求自己在哪一级台阶，和求解前一级台阶在哪一级的思路是完全一样的



存在递归终止条件

把问题分解为子问题，把子问题再分解为子子问题，一层一层分解下去，不能存在无限循环，这就需要有终止条件



还是上边的例子，第一级台阶是明确知道是第一级的也就是 f(1)=1，这就是递归的终止条件



编写递归代码

写递归的代码，最关键的就是写出递归公式、找到递归终止条件，剩下的将递归公式转化成代码就简单了



示例

以Leetcode上边的一道题为例

>假如这里有n个台阶，每次你可以跨1个台阶或者2个台阶，请问走这n个台阶有多少种走法？



如果有7个台阶，你可以 2，2，2，1 这样子上去，也可以 1，2，1，1，2 这样子上去，总之走法有很多，下边就是考虑如何通过代码来实现



经过思考我们可以知道，实际上，可以根据第一步的走法，把所有的走法分为两类

• 第一类是第一步走了1个台阶

• 第二类是第一步走了2个台阶



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

f(n) = f(n-1) + f(n-2)



有了递归公式，现在就差终止条件。首先，当只有一个台阶的时候，那肯定就只有一种走法，所以f(1) = 1



但是，只有这一个递归终止条件足够吗？肯定是不够的，比如现在考虑n=2和n=3的情况，靠这一个终止条件是否能够求出来

n=2
f(2) = f(1) + f(0)

如果递归终止条件只有一个f(1)=1，那 f(2)就无法求解了。所以除了f(1)=1 这一个递归终止条件外，还要有f(0)=1，表示走0个台阶有一种走法，不过这样子看起来就不符合正常的逻辑思维了。所以，可以把f(2)=2作为一种终止条件，表示走2个台阶，有两种走法，一步走完或者分两步来走



所以，最终得到的递归终止条件就是（可以找几个数字验证一下）

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



有了公式和递归终止条件，代码就很容易了

func StepEasy(n int) int {
	if n==1 {
		return 1
	}
	if n==2 {
		return 2
	}
	return StepEasy(n-1) + StepEasy(n-2)
}



分析

上边的这个例子，人脑几乎没办法把整个“递”和“归”的过程一步一步都想清楚



>计算机擅长做重复的事情，所以递归正和它的胃口。而我们人脑更喜欢平铺直叙的思维方式。当我们看到递归时，我们总想把递归平铺展开，脑子里就会循环，一层一层往下调，然后再一层一层返回，试图想搞清楚计算机每一步都是怎么执行的，这样就很容易被绕进去

>

>《数据结构与算法之美》



如果一个递归问题想试图去通过大脑去走一遍递归过程，实际上是进入了一个思维误区。很多时候，理解起来比较吃力，主要原因就是自己给自己制造了这种理解障碍



如果一个问题 A 可以分解为若干子问题 B、C、D，你可以假设子问题 B、C、D 已经解决，在此基础上思考如何解决问题 A。而且，你只需要思考问题 A 与子问题 B、C、D 两层之间的关系即可，不需要一层一层往下思考子问题与子子问题，子子问题与子子子问题之间的关系。屏蔽掉递归细节，这样子理解起来就简单多了



因此，*编写递归代码的关键是，只要遇到递归，我们就把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤*



总结

*写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码*



递归防坑指南



1、防止堆栈溢出



为什么递归代码容易造成堆栈溢出？

分享一个自己实际遇到的一个情况，之前公司举办过一次黑客马拉松的程序比赛，是一道求解数独的题，求解数独的过程就用到了递归，给你一些已知数，求解数独



如果给的已知数太少，就会导致你的解数独过程的递归次数特别多



在“栈”那一篇文章中有分享到，函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。系统栈或者虚拟机栈空间一般都不大。如果递归求解的数据规模很大，调用层次很深，一直压入栈，就会有堆栈溢出的风险



那么如何防止呢？



如何预防堆栈溢出？

也很简单，可以通过在代码中限制递归调用的最大深度的方式来解决这个问题。递归调用超过一定深度（比如 1000）之后，我们就不继续往下再递归了，直接返回报错



以上边的那个台阶为例

var depth = 0
func StepEasy(n int) int {
    depth++
	if depth > 100 {
		panic("递归次数太多")
	}
    
	if n==1 {
		return 1
	}
	if n==2 {
		return 2
	}
	return StepEasy(n-1) + StepEasy(n-2)
}



但这种做法并不能完全解决问题，因为最大允许的递归深度跟当前线程剩余的栈空间大小有关，事先无法计算。如果实时计算，代码过于复杂，就会影响代码的可读性。所以，如果最大深度比较小，比如 10、50，就可以用这种方法，否则这种方法并不是很实用



2、避免重复计算

使用递归时还会出现重复计算的问题，还是以走台阶的例子为例，假设n=6，递归分解一下的话，大概如下：



从图中，可以直观地看到，想要计算 f(5)，需要先计算 f(4) 和 f(3)，而计算 f(4) 还需要计算 f(3)，因此，f(3) 就被计算了很多次，这就是重复计算问题



为了避免重复计算，我们可以通过一个数据结构（比如散列表）来保存已经求解过的 f(k)。当递归调用到 f(k) 时，先看下是否已经求解过了。如果是，则直接从散列表中取值返回，不需要重复计算，这样就能避免刚讲的问题了



上边那个走台阶的问题，最终就可以优化成这样

package step
import "fmt"
//假如这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？如果有 7 个台阶，
//你可以 2，2，2，1 这样子上去，也可以 1，2，1，1，2 这样子上去，总之走法有很多，那如何用编程求得总共有多少种走法呢？
var depth = 0
var mapList = map[int]int{}
func Step(n int) int {
	depth++
	if depth > 100 {
		panic("递归次数太多")
	}
	if n == 1 {
		return 1
	} else if n==2 {
		return 2
	}
	if mapList[n] != 0 {
		return mapList[n]
	}
	res := Step(n-1)+ Step(n-2)
	mapList[n] = res
	fmt.Printf("step(%d) = %d", n, mapList[n])
	fmt.Println()
	return res
}



总结

除了堆栈溢出、重复计算这两个常见的问题。递归代码还有很多别的问题



在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本。在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销，比如我们前面讲到的电影院递归代码，空间复杂度并不是 O(1)，而是O(n)





*以上内容参考《数据结构与算法之美》-递归篇，对里边的例子进行了简单的改变，代码通过go来实现，总结性文字皆来自原文*