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

书旅 2020-11-11 15:03:10
算法 数据结构 数据 结构 法系


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

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,递归分解一下的话,大概如下:
image.png

从图中,可以直观地看到,想要计算 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来实现,总结性文字皆来自原文

版权声明
本文为[书旅]所创,转载请带上原文链接,感谢
https://segmentfault.com/a/1190000037799126

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云