用大白话如何理解递归的本质 ?

沙海
沙海
沙海
1532
文章
2
评论
2021年5月22日08:16:02
评论
3 4716字阅读15分43秒
摘要

速读摘要

速读摘要

电影院里面太黑了,现在你怎么办?前面的人也看不清啊,所以他也问他前面的人。调用一次就会在内存栈中保存一次现场数据,同样也会有可观的空间成本。递归的好处是代码简洁易理解,坏处就是上面的。迭代循环,对于线性结构的还好理解些,对于非线性结构的理解起来会更困难。

原文约 2709 | 图片 1 | 建议阅读 6 分钟 | 评价反馈

用大白话如何理解递归的本质 ?

程序IT圈

点击上方 蓝色字体,回复“加群

加入我们一起学习,天天进步

先来个场景:

下班了,你带着女友去电影院看电影~(没有女友?快私信我,组里各种白富美!加班没时间?快私信我,组里加班少!)女友问,咱两现在坐在第几排啊?电影院里面太黑了,看不清,没法数,现在你怎么办?

于是你开始展示你智慧的一面了,先问前排的人他是第几排,你想只要在他的数字上加一,就知道自己在哪一排了。

但是,前面的人也看不清啊,所以他也问他前面的人。就这样一排一排往前问~ 直到问到第一排的人,说我在第一排,然后再这样一排一排再把数字传回来。直到你前面的人告诉你他在哪一排,于是你就知道答案了。

这就是一个非常标准的递归求解问题的分解过程,去的过程叫“递”,回来的过程叫“归”,所以叫“递归”。

递归的本质:将原来的问题,转化为更小的同一问题。问题一点点变小,当问题变成最小级别之后,先解决最小级别的问题的答案,然后大一点的问题也有了答案,一点点的往上,这样原来的问题也就有了答案~

举例理解递归:数组求和

举个代码的例子理解下递归:对数组求和。

假设对 [1,2,3,4]求和,可以转化为 [2,3,4]的求和,这样问题就变得更小,直到转为空数组,空数组就是最小级别的问题,先解决最小级别的问题,然后大一点的问题也有了答案,一点点的,这样原来的问题也就有了答案~

伪代码:

=> [1,2,3,4]=> [1,2,3,4] = 1 + [2,3,4]=> [2,3,4] = 2 + [3,4]=> [3,4] = 3 + [4]=> [4] = 4 + []=> [] = 0=> [4] = 4 + 0=> [3,4] = 3 + 4=> [2,3,4] = 2 + 7=> [1,2,3,4] = 1 + 9=> 解决

写真实的代码:

function sum(arr) {  // 先解决最小级别的问题  if (arr.length === 0) {    return 0;  }  // 大的问题 转化为 更小的问题  return arr[0] + sum(arr.slice(1));}

可视化递归过程

上面看完之后,可能还是有点点蒙圈,感觉似懂非懂~

没事,可视化代码运行,就明白了!可视化的过程,也是调试的技巧!

先可视化上面的数组求和:

function sum(arr, depth) {  // 递归层级越深,缩进越长。同一层级的,缩进等长  const indent = "--".repeat(depth);  // 调用开始,输出一次  console.log(`${indent}Start Call: sum of [${arr}]`);  if (arr.length === 0) {    const res = 0;    // 返回之前,输出一次    console.log(`${indent}Return: sum of [${arr}] is ${res}`);    return res;  }  let res = sum(arr.slice(1), depth + 1);  // 调用之后,输出一次  console.log(`${indent}After Call: sum of [${arr.slice(1)}],sum is ${res}`);  res = arr[0] + res;  // 返回之前,输出一次  console.log(`${indent}Return: sum of [${arr}] is ${res}`);  return res;}sum([1, 2, 3, 4], 0);

执行代码:

Start Call: sum of [1,2,3,4]--Start Call: sum of [2,3,4]----Start Call: sum of [3,4]------Start Call: sum of [4]--------Start Call: sum of []  // 这里是最小级别的问题--------Return: sum of [] is 0 // 解决最小级别的问题------After Call: sum of [],sum is 0------Return: sum of [4] is 4----After Call: sum of [4],sum is 4----Return: sum of [3,4] is 7--After Call: sum of [3,4],sum is 7--Return: sum of [2,3,4] is 9After Call: sum of [2,3,4],sum is 9Return: sum of [1,2,3,4] is 10

再联系本文开头的话,“递”和“归”的过程,就能看出来了~

大问题转化为更小的同一问题,一直转化到最小级别的问题,先解决最小级别的问题,然后大一点的问题就解决了,一直到原先的问题就会被解决~

可视化代码的步骤:

  • 先给函数加个额外的参数:递归深度,表示递归到哪了

  • 递归深度,可以用字符串缩进可视化

  • 调用开始的时候,打印下当前的参数(可语义下)

  • 调用之后,打印下调用返回的结果和对应参数(可语义下)

  • 返回结果之前,打印下返回结果和对应参数(可语义下)

怎么写递归

两步:

  • 找到递归边界:找到最小级别的问题,并搞定答案

  • 找到递归式:将大问题转化为更小的同一问题(假设更小的问题有了答案,只想到第一层就行)

再举个例子:

有一组数:1,1,2,3,5,8,13,21........

问第 n 个数是什么?

细细看看,其实就是斐波拉契数列,后面一个数等于前两数之和。

  • 找到递归边界:找到最小级别的问题,并搞定答案

其实就是前两个数:

f(1) = 1;f(2) = 1;
  • 找到递归式:将大问题转化为更小的同一问题(假设更小的问题有了答案,只想到第一层就行)

第 n 个数就是前两数之和:

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

撸码:

function f(n) {  // 最小级别的问题,务必搞定答案  if (n === 1) return 1;  if (n === 2) return 1;  // 假设n-1和n-2都知道的话  return f(n - 1) + f(n - 2);}

可以试试可视化过程,这里我就不演示了,当作业了~

递归的缺陷和解决方案

两个大缺陷:

  • 堆栈溢出

  • 重复计算度高

可以看到,递归的过程就是函数调用的过程,反复调用函数,函数调用栈会很高,一定数量级之后,会溢栈,专业名词就是堆栈溢出,表现为代码报错了!

这种缺陷的一个解决办法是:提前规定最大深度,超过深度之后直接报错。当然这个最大深度不一定好估计。

// 全局变量,表示递归的深度。let depth = 0;function f(n) {  ++depth;  if (depth > 1000) throw Error('递归层次超过范围了');  if(n === 1) return 1  if(n === 2) return 1  return f(n-1) + f(n-2)}

重复计算度高怎么理解呢?

比如计算第 5 个数,等价于 f(3)+f(4),而f(4)等价于f(3)+f(2),注意这里的 f(3)出现了两次,这还只是计算第 5 个数,如果更大的话,会重复计算更多次!

这种缺陷的一个解决办法是:用哈希表保存已经求解过的 f(k),调用到 f(k) 时,哈希表有则直接返回,不需要重复计算了。当然代价是,空间复杂度变高。

let resolvedList = {};function f(n) {  if (n === 1) return 1;  if (n === 2) return 1;  // 保存过的话直接返回  if (resolvedList[n]) {    return resolvedList[n];  }  const res = f(n - 1) + f(n - 2);  // 没保存过的,保存下  resolvedList[n] = res;  return res;}

除了堆栈溢出、重复计算度这两个大问题,时间上,过多的函数调用会积聚成一个可观的时间成本;空间上,调用一次就会在内存栈中保存一次现场数据,同样也会有可观的空间成本。

怎么将递归代码改写为非递归代码

递归的好处是代码简洁易理解,坏处就是上面的。能不能将其转化为非递归代码呢?答案是肯定的!递归的过程可以理解为函数调用栈的过程,我们可以手动模拟进栈出栈,也就是迭代循环!

// 数组求和:/*function sum(arr) {  if (arr.length === 0) return 0;  return arr[0] + sum(arr.slice(1));}*/function sum(arr) {  if (n === 0) return 0;  let res = 0;  for (let i = 0; i <= arr.length; i++) {    // 手动迭代res    res = arr[i] + res;  }}
// 斐波拉契数列:/*function f(n) {  if (n === 1) return 1;  if (n === 2) return 2;  return f(n - 1) + f(n - 2);}*/function f(n) {  if (n === 1) return 1;  if (n === 2) return 1;  let res = 0;  let pre = 1;  let prepre = 1;  for (let i = 3; i <= n; ++i) {    // 手动迭代res    res = pre + prepre;    prepre = pre;    pre = res;  }  return res;}

“手动”递归,并不是说没有缺点,虽然没有那么多函数调用,但是重复计算度依然很高。另外,迭代循环,对于线性结构的还好理解些,对于非线性结构的理解起来会更困难。

引用

  • ACM 亚洲区奖牌获得者 liuyubobobo 的玩转数据结构_5-3

  • 前 Google 工程师王争的数据结构与算法之美_10

来源:颜酱

https://juejin.cn/post/6948718907918123044

近期技术热文

1、推荐一款神器 Typora !2、最新TIOBE 5月榜单:Java语言掉到第三 !3、抖音服务器带宽有多大,为什么能够供那么多人同时刷?4、墙裂建议收藏,100道Python练手题目

最后给大家送下福利,大家可以关注Java后端编程公众号,在后台回复 “Java”可以获取一份我整理的最新Java面试题资料。

最近面试BAT,整理一份面试资料《Java面试BAT通关手册》,覆盖了Java核心技术、JVM、Java并发、SSM、微服务、数据库、数据结构等等。获取方式:关注公众号并回复 java 领取,更多内容陆续奉上。

明天见(。・ω・。)ノ♡

继续阅读
weinxin
资源分享QQ群
本站是一个IT技术分享社区, 会经常分享资源和教程; 分享的时代, 请别再沉默!
沙海
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: