数据结构与算法系列之递归(GO)

微信扫一扫,分享到朋友圈

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

有疑问加站长微信联系(非本文作者)

阿里资深技术专家:在各阶段中,3年经验的java程序员应该具备哪些技术能力

上一篇

《赤狐书生》曝“群妖连环计”预告陈立农遭遇哈妮克孜“美人计”

下一篇

你也可能喜欢

数据结构与算法系列之递归(GO)

长按储存图像,分享给朋友