简单易懂的现代魔法-递归

Joyven 发布于2019-08-23 10:32 / 2631人阅读

摘要：完整的一次调用流程递归调用栈递归同样使用调用栈我们来分析下阶乘的调用栈直接看图递归注意事项递归会导致程序的性能变低如果递归嵌套很深，那么调用栈会很长，这将占用大量内存，可能会导致栈溢出

平时在前端开发中，好像也没啥用到递归的地方。不过这并不代表递归不重要，如果你看过一些框架的源码，就会经常见到它的影子：比如渲染虚拟DOM的render函数，webpack中require依赖分析，Koa2洋葱式的中间件模型，其实都运用到了递归算法。

博客原文

递归概念

那么递归到底是啥？先上两张图：

图1：

图2：

递归，就是在运行的过程中调用自己

我们来看个最简单的阶乘函数：

5! = 5 * 4 * 3 * 2 * 1

function factorial(num) {
    if (num === 1) { // 基线条件
        return 1;
    }

    // 递归条件
    return num * factorial(num-1);
}

factorial(5);

一个常规的递归函数都有两部分：

基线条件(if (num === 1))：保证函数不再调用自己，避免无限循环

递归条件(num * factorial(num-1))：保证函数能够调用自己

调用栈

栈是一种先进后出的数据结构，它只有两种操作，出栈和入栈

const nekopara = ["chocolat", "Coconut"];
nekopara.push("vanilla"); // 入栈
nekopara.pop(); // 出栈

代码在运行过程中，会有一个叫做调用栈(call stack)的概念。

function greet(name) {
    console.log(`hello, ${name}!`)
    greet2(name);
    console.log(`getting ready to say bye`);
    bye();
}

function greet2(name) {
    console.log(`how are you, ${name}?`);
}

function bye() {
    console.log(`bye`);
}

greet("deepred");

调用greet("deepred")时，计算机会首先给该函数分配一块内存，并将变量名name设置为deepred

每当调用函数时，都会分配一个内存块并将涉及到的变量值存储到内存中。

打印hello, deepred后，调用了greet2("deepred")。同样，计算机再次分配了一块内存，并且该内存块位于第一个内存块上面。

调用栈的最上面表示当前运行的函数，如图所示，现在正在运行的是greet2函数，打印输出how are you, deepred?后，函数greet2执行完毕，栈顶的内存块被弹出。

现在栈顶的内存块又变回greet，这意味着我们从greet2的函数中跳出，再次返回到了greet。

我们在greet中调用了greet2时，greet只执行了一部分。

特别注意：调用另外一个函数时，当前函数暂停并且处于未完成状态，暂停函数的所有变量的值仍然在内存中。

执行完greet2后，我们回到了greet，并从离开的地方开始接着往下执行：首先打印getting ready to say bye，然后调用bye函数。

在栈顶添加了bye函数的内存块后，开始执行bye函数，打印bye，然后函数返回，内存块被弹出。

我们又再次回到了greet中，这次没有其他要运行的代码了，于是从greet函数中返回，内存块被弹出，调用栈最后为空。

完整的一次调用流程：

递归调用栈

递归同样使用调用栈

我们来分析下阶乘fact(3)的调用栈

function fact(num) {
   if (num === 1) { 
       return 1;
   }
   return num * fact(num-1);
}

fact(3);

直接看图:

递归注意事项

递归会导致程序的性能变低

如果递归嵌套很深，那么调用栈会很长，这将占用大量内存，可能会导致栈溢出

云服务器 GPU云服务器创造与魔法云鸟便宜的服务器创造与魔法所有服务器的云鸟在哪易懂深度学习最易懂

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/96445.html

用最简单易懂的道理告诉你，为什么JavaScript在现代引擎（V8，JavaScriptCore）

摘要：代码在本文最后，首先是，编译出字节码耗时约，运行字节码耗时约，。也有解释过程，字节码需要由虚拟机解释执行。而引擎的做法是更接近二哥的，在编译阶段的过程是源码抽象语法树字节码中间代码。于是大量的字节码优化措施被延后，比如。简单性能测试首先，我们先来做一个简单的性能测试，对比一下Java，JavaScript，PHP，Ruby这四门语言。这个性能测试，是计算斐波那契数列（兔子数列）。比...

Moxmi 2019-08-19 18:21 评论0 收藏0
手摸手教你用 js 写一个 js 解释器

摘要：手摸手教你用写一个解释器用来编译看起来是个高大上的东西，实际原理其实很简单，无非就是利用对象属性可以用字符串表示这个特性来实现的黑魔法罢了。手摸手教你用 js 写一个 js 解释器用 js 来编译 js 看起来是个高大上的东西，实际原理其实很简单，无非就是利用 js 对象属性可以用字符串表示这个特性来实现的黑魔法罢了。之所以看起来那么深奥, 大概是由于网上现有的教程，都是动不...

hss01248 2019-08-23 17:04 评论0 收藏0
窥探 Script 标签（步入现代 Web 开发的魔法世界）

摘要：而且默认带有执行的顺序是，，即便是内联的，依然具有属性。模块脚本只会执行一次必须符合同源策略模块脚本在跨域的时候默认是不带的。通常被用作脚本被禁用的回退方案。最后标签真的令人感到兴奋。窥探 Script 标签 0x01 什么是 script 标签？ script 标签允许你包含一些动态脚本或数据块到文档中，script 标签是非闭合的，你也可以将动态脚本或数据块当做 script 的...

Terry_Tai 2019-08-20 18:17 评论0 收藏0
窥探 Script 标签（步入现代 Web 开发的魔法世界）

摘要：而且默认带有执行的顺序是，，即便是内联的，依然具有属性。模块脚本只会执行一次必须符合同源策略模块脚本在跨域的时候默认是不带的。通常被用作脚本被禁用的回退方案。最后标签真的令人感到兴奋。窥探 Script 标签 0x01 什么是 script 标签？ script 标签允许你包含一些动态脚本或数据块到文档中，script 标签是非闭合的，你也可以将动态脚本或数据块当做 script 的...

gaosboy 2019-08-01 17:13 评论0 收藏0