关于数据结构和算法:数据结构与算法系列之递归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 来实现，总结性文字皆来自原文