我希望自己作为一名自学成才的开发人员读过的递归解释

#1 函数的返回值

#2 调用堆栈

我尝试了好几次才理解递归函数。

当我理解了它的工作原理后，我发现我还没有完全理解两件事：

1. 函数的返回值
2. 调用堆栈

一旦我理解了这两个，递归就变得有意义了。

如果我可以回去的话，这篇文章就是我教初学者递归的方法。

#1 函数的返回值

当函数返回一个值时，函数本身会被返回值所取代。

让我试着举例说明：

这是一个返回数字平方的函数

function square(x) => x * x;

这：

const num = 1 + square(3);

与以下内容相同：

const num = 1 + 9;

square(3)被 9“替换”，因为 9 是该函数返回的值。

酷吗？太棒了。

你还记得数学里有时顺序或运算很重要吗？使用函数时就是这种情况。代码解释器square(3)在知道返回值之前不能对某个值加square(3)1。所以函数必须在同一行的其他计算之前执行。

例子：

function square(x) => x * x; //line 1
const num = 1 + square(3);   //line 2
console.log(num) //10        //line 3

解释器将按照以下顺序运行上述代码：

1. 第 1 行（读取函数声明）
2. 第 2 行（哦，这里有一个函数，让我们调用这个函数并将值 3 传递给它）
3. 第 1 行（函数以 3 调用并返回值 9）
4. 第 2 行（它用 9 替换函数，现在可以计算 9 + 1 并将其分配给 num）
5. 第 3 行最后我们将 10 记录到控制台。

要点是，每次有函数调用时，解释器都会：

• 在该行停止并调用该函数
• 它使用传入的值（如果有）运行函数代码
• 它回到调用它的那行
• 用返回值替换函数调用
• 从那里继续

理解这一点对于理解递归至关重要（这是我遇到的问题之一，它使我更难理解递归）。

#2 调用堆栈

调用堆栈是解释器（如该浏览器中的 javascript 解释器）跟踪脚本调用的函数的方式。

这就是解释器知道如何返回到调用该函数的那一行的方式。

我想把它想象成一个盒子，用来存储你读过的书以及你在哪一页、哪一行停留。

假设您在当地图书馆。

你开始读《人类简史》。第72页第87行提到了双门齿兽（地球上最大的有袋动物），这激起了你的好奇心。于是你用记号笔在页面上记下你读到的那一行，然后把书放进了盒子里。

然后你找到一本关于双门齿兽的书。但在第94页第138行，它提到了巨型树懒，好奇心又一次涌上心头。你用记号笔在第94页写下你当前所在的行，然后把它放进了盒子里。

当你读到更多关于巨型树懒的内容时，你意识到该回家了。你又在第121页第147行放了一块白板，然后把书放进了盒子里。

第二天早上，你冲到图书馆完成你的阅读。

你怎么知道你上次读到哪本书、哪页、哪一行了？因为你把一堆书和马克笔都整理好了，所以答案很简单。只要从盒子里拿出最上面的那本书，里面的马克笔就能告诉你读到哪页、哪一行了。

知道你可以回到最初的书（《人类简史》）并继续阅读直到最后（或直到好奇心再次袭来）

类比如下：

1. 该框是调用堆栈
2. 每本书都是一个函数调用
3. 每个标记表示该函数在哪一行被调用。

如果我把这个例子翻译成代码，它看起来会像这样：

function readSapiens(){
   //read until page 72 line 87
   readDiprotodonsBook();
   //finish reading sapiens(when we are back from reading about diprotodons)
}

function readDiprotodonsBook(){
   //read until page 94 line 138
   readGiatSlothsBook();
   //finish reading diprotodon's book(when we are back from reading about giant sloths)
}

function readGiatSlothsBook(){
   //read until page 121 line 147
   debugger
}

readSapiens();

如果您现在按下 f12，复制此代码，将其粘贴到控制台上，按下回车键，然后转到“源”选项卡，您就可以看到调用堆栈。

它看起来会像这样：

代码在第三个函数调用中暂停。

看看有没有魔法，一切都建立在数据结构之上。

现在我们准备讨论一个实际的递归函数示例。

基本示例

我能想到的最简单的例子是一个将所有数字相加直到等于你传入的数字的函数。

function addNums(x){
   if(x === 1) return x;
   return x + addNums(x - 1);
}

注意：为了简化示例，我没有考虑 0 或负数。

addNums(3) //6
addNums(5) //15

让我们逐行看一下：

function addNums(x){          //line 1
   if(x === 1) return x;      //line 2
   return x + addNums(x - 1); //line 3
}                             //line 4
                              //line 5
let sumThree = addNums(3);    //line 6
console.log(sumThree); //6    //line 7

1. [第 1 至 5 行]：顺利执行，它只是声明了函数（现在我们可以在需要时调用它）

2. [第 6 行]：解释器声明了变量sumThree，但在赋值之前，addNums(3)它意识到这是一个函数，因此必须先调用该函数（将 3 传递给它），然后将返回值赋给变量sumThree

2.1. [等待第 6 行]：它调用第 1 行的函数，并将 3 传递给它。3 不等于 1，所以我们跳过了第 2 行。在第 3 行我们应该返回，3 + addNums(3 - 1)但需要等待，因为这是另一个函数调用。所以它必须先调用它，并将 2 传递给它。

2.2. [等待第 6 行 [等待第 3 行]]：它调用第 1 行的函数，并将 2 传递给它。2 不等于 1，所以我们跳过了第 2 行。在第 3 行我们应该返回，2 + addNums(2 - 1)但需要等待，因为这是另一个函数调用。所以它必须先调用它并将 1 传递给它。

2.3. [等待第 6 行 [等待第 3 行 [等待第 3 行]]]：它调用第 1 行的函数，并将 1 传递给它。这次我们遇到了起始条件。1 === 1 为真，因此我们第一次从函数调用中返回了一个值。

2.4. [等待第 6 行 [等待第 3 行]]：它回到上一个函数调用的第 3 行。它现在可以计算了，2 + addNums(2 - 1)因为它知道addNums(2 - 1)是1。所以这个函数现在可以返回3。

2.5. [等待第 6 行]：最后，它回到第 6 行的初始调用。它现在可以计算了3 + addNums(3 - 1)，因为它知道了addNums(3 - 1)。3所以这个函数现在可以最终返回 了6。

1. [第 7 行]：它记录6到控制台。

我也尝试以视觉方式解释它（尽我所能），请看一看：

结论

如果你读到这里，首先我要感谢你，这对我来说意义重大。其次，如果你在阅读这篇文章时遇到任何困惑，能帮我个忙吗？

留下一条简短的评论，告诉我在哪里失去了你。

我会尝试改进这篇文章，以便它可以帮助那些像我一样曾经很难理解递归的人。

再次感谢您的阅读！

如果你喜欢这篇文章：

留言（你可以直接打个招呼！）
让我们在 Twitter 上联系@theguspear

下周见，

格斯。