打开APP
userphoto
未登录

开通VIP，畅享免费电子书等14项超值服

开通VIP

首页

好书

留言交流

下载APP

联系客服
用大白话如何理解递归的本质 ？
userphoto 关注

先来个场景：

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

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

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

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

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

举例理解递归：数组求和

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

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

伪代码：

  1. => [1,2,3,4]
  2. => [1,2,3,4] = 1 + [2,3,4]
  3. => [2,3,4] = 2 + [3,4]
  4. => [3,4] = 3 + [4]
  5. => [4] = 4 + []
  6. => [] = 0
  7. => [4] = 4 + 0
  8. => [3,4] = 3 + 4
  9. => [2,3,4] = 2 + 7
  10. => [1,2,3,4] = 1 + 9
  11. => 解决

写真实的代码：

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

可视化递归过程

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

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

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

  1. function sum(arr, depth) {
  2.   // 递归层级越深，缩进越长。同一层级的，缩进等长
  3.   const indent = '--'.repeat(depth);
  4.   // 调用开始，输出一次
  5.   console.log(`${indent}Start Call: sum of [${arr}]`);
  6.   if (arr.length === 0) {
  7.     const res = 0;
  8.     // 返回之前，输出一次
  9.     console.log(`${indent}Return: sum of [${arr}] is ${res}`);
  10.     return res;
  11.   }
  12.   let res = sum(arr.slice(1), depth + 1);
  13.   // 调用之后，输出一次
  14.   console.log(`${indent}After Call: sum of [${arr.slice(1)}],sum is ${res}`);
  15.   res = arr[0] + res;
  16.   // 返回之前，输出一次
  17.   console.log(`${indent}Return: sum of [${arr}] is ${res}`);
  18.   return res;
  19. }
  20. sum([1, 2, 3, 4], 0);

执行代码：

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

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

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

可视化代码的步骤：

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

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

  • 调用开始的时候，打印下当前的参数（可语义下）

  • 调用之后，打印下调用返回的结果和对应参数（可语义下）

  • 返回结果之前，打印下返回结果和对应参数（可语义下）

怎么写递归

两步：

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

  • 找到递归式：将大问题转化为更小的同一问题（假设更小的问题有了答案，只想到第一层就行）

再举个例子：

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

问第 n 个数是什么？

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

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

其实就是前两个数：

  1. f(1) = 1;
  2. f(2) = 1;

  • 找到递归式：将大问题转化为更小的同一问题（假设更小的问题有了答案，只想到第一层就行）

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

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

撸码：

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

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

递归的缺陷和解决方案

两个大缺陷：

  • 堆栈溢出

  • 重复计算度高

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

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

  1. // 全局变量，表示递归的深度。
  2. let depth = 0;
  4. function f(n) {
  5.   ++depth；
  6.   if (depth > 1000) throw Error('递归层次超过范围了');
  7.   if(n === 1) return 1
  8.   if(n === 2) return 1
  9.   return f(n-1) + f(n-2)
  10. }

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

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

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

  1. let resolvedList = {};
  3. function f(n) {
  4.   if (n === 1) return 1;
  5.   if (n === 2) return 1;
  6.   // 保存过的话直接返回
  7.   if (resolvedList[n]) {
  8.     return resolvedList[n];
  9.   }
  10.   const res = f(n - 1) + f(n - 2);
  11.   // 没保存过的，保存下
  12.   resolvedList[n] = res;
  13.   return res;
  14. }

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

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

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

  1. // 数组求和：
  2. /*
  3. function sum(arr) {
  4.   if (arr.length === 0) return 0;
  5.   return arr[0] + sum(arr.slice(1));
  6. }
  7. */
  8. function sum(arr) {
  9.   if (n === 0) return 0;
  10.   let res = 0;
  11.   for (let i = 0; i <= arr.length; i++) {
  12.     // 手动迭代res
  13.     res = arr[i] + res;
  14.   }
  15. }
  1. // 斐波拉契数列：
  2. /*
  3. function f(n) {
  4.   if (n === 1) return 1;
  5.   if (n === 2) return 2;
  6.   return f(n - 1) + f(n - 2);
  7. }
  8. */
  9. function f(n) {
  10.   if (n === 1) return 1;
  11.   if (n === 2) return 1;
  13.   let res = 0;
  14.   let pre = 1;
  15.   let prepre = 1;
  16.   for (let i = 3; i <= n; ++i) {
  17.     // 手动迭代res
  18.     res = pre + prepre;
  19.     prepre = pre;
  20.     pre = res;
  21.   }
  22.   return res;
  23. }

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

引用

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

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

来源：颜酱

https://juejin.cn/post/6948718907918123044

本站仅提供存储服务，所有内容均由用户发布，如发现有害或侵权内容，请点击举报。
打开APP，阅读全文并永久保存 查看更多类似文章
猜你喜欢
类似文章
【热】打开小程序，算一算2024你的财运
字节一面：非递归手写快速排序
统计网页标签元素，使用次数，排序，递归骚操作——进阶高级前端工程师
记一次笔试题
用VBA实现Excel函数：SUM
递归函数问题
一文讲透【递归】与【动态规划】！
更多类似文章 >>
生活服务
热点新闻
留言交流
回顶部
联系我们
分享 收藏 导长图 关注 下载文章
绑定账号成功
后续可登录账号畅享VIP特权！
如果VIP功能使用有故障，
可点击这里联系客服！

联系客服