• 掌握递归调用栈思想 由浅入深研究递归

    小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

    本文已参与「掘力星计划」，赢取创作大礼包，挑战创作激励金。

    递归是超级强大的一种解决问题的思路

    作为一只面向找工作刷题的前端菜狗 刚开始刷题的时候我经常在暴力迭代A掉一道力扣之后抱着试试看的想法去尝试“递归解法”

    然后自闭掉

    流下了不学无术的泪水.jpg

    经过几个月的刷题 我慢慢了解到——

    • 递归函数们都被暂存在栈中 等触发边界条件之后开始弹栈并执行栈中的函数

    • 从最里面那层开始研究 return 的内容更好想

    ...

    研究递归的题目倒蛮像抽丝剥茧的🤔

    之前看过不少讲递归的文章 但是总感觉 要不就是大神段位比我高太多 内容有点不好理解 要不就是例子太少 大量理论往我脸上一怼 瞬间懵逼😂

    所以本篇文章想写一篇就算是小白也能很舒服地理解的“递归” 同时结合着例子 大家可以先尝试着自己写一下递归解法 再画个图 如果不明白再来看看解法🙌

    另外 本篇文章打算对不同题型的递归做法进行研究(随着我碰到不同题型中的递归方法 我会更新到本文中 当作是日后想不通递归法的一个小手册吧！)—— 数组 链表 二叉树...中的递归

    读过本文 你会收获——

    • 利用栈的思想 肉脑轻松想递归(当然是简单一点的递归啦🤣)

    • 使用递归解决数组循环遍历问题 —— 最基础 用来入门递归思想再合适不过了😄

    之后我还会用本文的思想去解决更多的问题

    • 使用递归解决有序链表合并问题 —— 使用递归跳过复杂的链表遍历 轻松获得答案😎

    • 使用递归解决二叉树问题 —— 二叉树的题目基本就离不开递归了XD 所以 想做出来二叉树？先把递归研究明白~🤔

    • 使用递归解决排序问题

    1.理解递归函数所处的调用栈

    前段时间学习到 JavaScript的 “执行上下文栈” 发现其可以完美解释递归函数的执行

    首先我们说 一点点 理论的东西(之前学习过的文章里看到的解释 感觉很有道理~)

    递归就像是“查字典” 我们看到一句话 发现其中有不懂的词 于是开始查字典(入栈递归函数)

    查完以后发现字典的解释里还有不懂的词 于是继续查(再入栈一个递归函数)

    ...省略n个层层查找(也就是不断的递归函数入栈)

    终于 我们弄懂了一个词(抵达了base case——用于告诉递归函数何时结束) ✨

    之后利用这个词再去理解上层的那个词(不断地进行递归函数出栈并执行递归函数 返回值传给调用栈中的函数)

    直到我们理解这句话的意思(所有调用函数全部出栈 返回最终结果)递归函数完成了它的使命~

    总结：递归分两步——

    • 递：“查字典” 不断将递归函数入栈

    • 归：“通过字典获取内容 来理解句子”：将递归函数出栈并一个个地返回结果供后续函数使用

    口说无凭 举个例子 上个例子 画个图——

    利用调用栈的思想秒杀递归

    来看道题

    1. foo(1);
    2. function foo(i) {
    3.     if (i == 4) {
    4.         return;
    5.     }
    6.     console.log('foo() begin:' + i);
    7.     foo(i + 1);
    8.     console.log('foo() end:' + i);
    9. }
    10. // 输出 ? 
    11. 复制代码

    借助调用栈很好想！(别嫌我图丑哈😢)

    image.png

    很明显最终结果是1 2 3 3 2 1

    其实这里如果有动图就更清楚了 但是我懒我相信大家都能脑补出来的！😘

    根据黑色箭头的方向 递归函数先入栈再出栈~

    2.利用递归代替循环解决数组问题

    这里利用三个很简单的数组操作 来帮助大家加深对递归的印象

    灵感来自 freecodecamp 使用递归代替循环 使用递归创建一个倒计时 使用递归来创建一个数字序列 (顺便给前端学习者们安利一波这个333k star数的宝藏学习平台❤️)

    利用递归计算数组前n个元素的和

    这题用循环的方式大家肯定都能秒杀

    正因为它的简单 所以我们可以利用其入门/练习 递归思想

    1. // 题目
    2. 写一个递归函数，`sum(arr, n)`，返回递归调用数组 `arr` 的前 `n` 个元素和。
    3. 复制代码

    递归秒杀

    1. function sum(arr, n){
    2.     if(n <= 0){
    3.         return 0;
    4.     }
    5.     else{
    6.         return sum(arr, n - 1) + arr[n - 1];
    7.     }
    8. }
    9. sum([6, 6, 6, 6], 3);
    10. 复制代码

    画一下递归调用栈

    依旧是不要嫌弃我的图丑😂

    image.png

    使用递归创建一个倒计时

    上面那题太简单？

    再来一道(好吧还是很简单😂)

    1. // 题目
    2. 已经定义了一个函数 `countdown`，函数有一个参数(`n`)。 
    3. 函数应该基于参数 `n` 递归调用返回 `n` 到 `1` 的连续数字的数组。 
    4. 如果函数以小于 1 的参数调用，函数应该返回空数组。 
    5.  
    6. 比如，用 `n = 5` 调用函数应该返回数组 `[5, 4, 3, 2, 1]`。 
    7. 函数必需使用递归函数调用自身，不能使用任何形式的循环。
    8. 复制代码

    递归秒杀

    循环？才不要用 (其实是因为题目不让用😐)

    递归直接秒杀！

    常规方法

    1. // 01 先将函数入栈(递 的过程) n = 0 时 countdown就是 []
    2. // 出栈的时候将值插入数组中(归 的过程)
    3. function countdown(n){
    4.     if(n <= 0){
    5.         return [];
    6.     }
    7.     else{
    8.         const countArray = countdown(n - 1);
    9.         countArray.unshift(n);
    10.         // 需要头插 因为是倒序的数组嘛~
    11.         // countArray.splice(0, 0, n);
    12.         // 这样也可以达到头插的效果
    13.         return countArray;
    14.     }
    15. }
    16. countdown(5);//[5,4,3,2,1]
    17. 复制代码

    三元表达式一行秒杀

    1. // 02 更为简洁的一行代码秒杀法
    2. // n = 0时 返回值为 [5,...[]] 之后随着递归函数出栈 返回值数组逐渐插入数字
    3. function countdown(n){
    4. 	return n <= 0 ? [] : [n].concat(countdown(n - 1));
    5.     // return n <= 0? [] : [n, ...countdown(n - 1)];// 更加简洁的展开运算符~
    6. }
    7. 复制代码

    画一下递归调用栈

    image.png

    使用递归来创建一个数字序列

    最后来练一道题

    到了这里 建议大家点开上面☝️的链接自己做一下试试！

    一边画调用栈 一边写代码 很快啊！就做出来了~😎

    递归秒杀

    常规解法

    1. function rangeOfNumbers(startNum, endNum) {
    2.   if(startNum === endNum){
    3.     return [startNum];
    4.   }
    5.   else{
    6.     const countArray = rangeOfNumbers(startNum + 1, endNum);
    7.     countArray.unshift(startNum)
    8.     return countArray;
    9.   }
    10. };
    11. 复制代码

    三元表达式一行秒杀

    1. function rangeOfNumbers(startNum, endNum) {
    2.     return startNum === endNum 
    3.       ? [startNum] 
    4.       :rangeOfNumbers(startNum, endNum - 1).concat(endNum);
    5.       // : [...rangeOfNumbers(startNum, endNum - 1), endNum];  
    6. };
    7.  
    8. rangeOfNumbers(1,3)
    9. 复制代码

    为了美观拆分了一下~

    画一下递归调用栈

    前两个图都是常规方法的 这个来画一个三元表达式的

    害！其实都一样

    image.png

    3.小结 & 可以使用递归解决的问题

    本文涉及的递归都是 最最最基础的递归 但是工欲善其事必先利其器！

    我们要先把基础的递归思想理解得透透 再去实践更加复杂的题型

    学习了递归法之后可以尝试解决的题型——

    (持续更新中)

    easy

    推荐看这个 动图题解 看完不明白 我自己吃了它 满意了吧🍉

    1. var reverseList = function(head) {
    2.     // “递”的过程
    3.     if(head === null || head.next === null){
    4.         return head;
    5.     }
    6.     let newHead = reverseList(head.next);// 把head.next这个子问题传进去 
    7.     // 在弹出最顶部的function(链表末尾处节点)之后 返回的节点赋给了newHead 
    8.     // “归”的过程
    9.     head.next.next = head;
    10.     head.next = null;
    11.     return newHead;
    12. };
    13. 复制代码

    medium

    总之 这上面的题目都是最基础最基础的递归题目

    掌握了上面的递归调用栈的思路 理解它们的用法很简单 但是——

    真的拿到一道题目 你能想到用递归去做嘛 能想明白内层的操作是哪样的嘛 ？ 根据本文的知识点 还是不能的...

    所以说 还是得多做题 多去思考呐！

    来源：https://juejin.cn/post/7016324095843237901
  • 相关阅读:
    1087 有多少不同的值
    SpringMVC异常处理器
    可以群发消息的微信营销软件
    设置RabbitMQ超时时间
    贪心 Leetcode 135 分发糖果
    php二维数组查找某个id=1的元素
    双碳红利+基建大年 | 图扑深耕水利水电绿色智能装备领域
    目标检测YOLO实战应用案例100讲-基于小样本学习和空间约束的濒危动物目标检测(续)
    tensorrt 高级(1):完整的分类器实现
    用Python做了个图片识别系统(附源码)
  • 原文地址：https://blog.csdn.net/china_coding/article/details/126516450