这里指的通用套路是把递归执行改为在一个函数中循环执行。出于好奇心想找出一种把递归改为非递归的通用形式，并学习其中的思路。在网上找了几篇文章，联合函数调用栈的了解，感觉本人总结的应该比拟全面了，所以记录下来跟大家交换下。
递归执行和一般嵌套执行的区别
先看一段简略的代码，计算阶乘的递归函数：
// n! = n * (n - 1) * (n - 2) * ... * 1function getFactorial(n) { if (n === 1) { return 1; } else { return n * getFactorial(n - 1); }}递归调用简略点来说就是函数在执行过程中调用了本身。在下一次调用中如果没达到设定的递归完结条件，这个过程会始终继续上来；当递归条件完结时，调用链条中的函数会一个接一个的返回。如以上的代码，当 n === 1 时，就会触发递归的完结条件。
这里咱们思考一下，递归函数的执行跟一般的函数嵌套执行有什么不同？:thinking:
其实没什么本质区别，递归调用和一般函数嵌套调用的层数一样也是无限的，层数的多少由递归完结条件来决定，无非是递归是本身调用本身（直觉上是代码的执行又回到了后面的行数）。接下咱们康康函数嵌套执行时产生了什么。
计算机是如何嵌套执行函数的？
如果你理解计算机执行汇编/机器码的原理就会晓得我接下来可能会说运行时函数调用栈。不过我打算用一种简略的形容来疏导你明确或加深印象。
首先，我先问个问题：一个函数在某一次的执行过程中，是什么货色让这一次执行与另外一次执行是有所差异的？
简略点来说，能够把这个问题了解为函数执行上下文。这个上下文有以下内容：
- 参数；
- 函数体中定义的变量；
- 返回值；
举个函数嵌套执行的栗子，a 函数以后在执行中，这个时候其中有条语句要执行 b 函数，这个时候能够简略了解为计算机做了以下的事件：
- 保留 a 函数的执行上下文；
- 切换到 b 函数的上下文；
- 代码执行来到了 b 函数的结尾，b 函数执行完并返回值；
- 切换回 a 函数的上下文，继续执行 a 函数残余的代码；
这个过程就是运行时函数调用栈，用栈这种数据结构来实现了上下文的切换。
咱们下面说到过递归调用能够类比为一般嵌套调用，无非是这一次的执行上下文切换到了下一次的执行上下文，并且留神还有代码执行的管制（后面说过，递归是又回到了后面行数执行）。通过以上的形容咱们能够失去一些思路，模仿递归，要解决两个次要问题：
- 模仿函数调用栈，切换执行上下文；
- 管制语句的执行程序，从前面的代码回到后面的代码执行；
执行上下文的切换，能够用栈来模仿。那么如何管制语句的执行程序呢？上面来介绍一种 Continuation 技术。
Continuation
来看个示例：
function test() { console.log(1); console.log(2); console.log(3);}以上的输入是 123，咱们当初要从新封装一个函数，内容一样，然而扭转这三句代码的执行程序，2 输入后持续回到 1，第二次输入 2 时再持续输入 3 并完结，也就是输入 12123。当然，不是要你反复写多余的 console.log 的。
计算机是通过 PC（Program Counter） 寄存器来获得下一条执行指令的地址。也就是说咱们要找到一种模仿 PC 寄存器的工作的计划，看上面的代码：
function test2() { let continuation = 0; let count = 0; while (true) { switch (continuation) { case 0: console.log(1); continuation = 1; break; case 1: console.log(2); count++; continuation = count < 2 ? 0 : 2; break; case 2: console.log(3); return; } }}以上的形式就是用 continuation 变量来模仿 PC 寄存器的操作。依据逻辑来改变程序的执行门路，就能够模仿代码在咱们想要的行数继续执行。上面就联合 Continuation 和模仿栈来康康怎么套路改写递归函数。
改写递归函数
先来看看套路的模板代码：
function example(...args) { const $stack = []; // 模仿栈操作，切换函数上下文。 let $result; // 记录每一次函数的执行后果。 /** * 调用递归函数，压入新的函数上下文，入栈操作。 * 函数的参数、函数外面申明的变量都要放入上下文中。 */ const $call = (...args) => { $stack.push({ continuation: 0, ...args }); }; /** * 递归函数执行结束，切换为上一次的函数上下文，出栈操作。 * 并记录函数的返回值。 */ const $return = result => { $stack.pop(); $result = result; }; // 第一次调用。 $call(...args); while ($stack.length > 0) { const current = $stack[$stack.length - 1]; switch (current.continuation) { // 将递归函数的代码拆分，利用 continuation 控制代码执行。 // ... } } // 返回最初的后果。 return $result;}// 执行 example(...) 开始调用“递归”函数。通过以上的代码能够看出，模板就是利用后面说到的两点来改写递归函数：
- 模仿函数调用栈，切换执行上下文；
- 利用 Continuation 技术管制语句的执行程序；
那么后面的阶乘递归函数用这个模板来改写后是这个样子的：
// n! = n * (n - 1) * (n - 2) * ... * 1function getFactorial(n) { if (n === 1) { return 1; } else { return n * getFactorial(n - 1); }}// 改为非递归。function getFactorial2(n) { const $stack = []; let $result; const $call = n => { $stack.push({ continuation: 0, n }); }; const $return = result => { $stack.pop(); $result = result; }; $call(n); while ($stack.length > 0) { const current = $stack[$stack.length - 1]; switch (current.continuation) { case 0: { const { n } = current; if (n === 1) { $return(1); } else { $call(n - 1); current.continuation = 1; } break; } case 1: { const { n } = current; $return(n * $result); break; } } } return $result;}这里了解的重点在于如何拆分和改写代码，原则上调用递归函数的中央都要拆开。比方原代码是 return n * getFactorial(n - 1);，拆成了两个局部：
case 0: { const { n } = current; if (n === 1) { $return(1); } else { $call(n - 1); // 调用递归函数的中央。 current.continuation = 1; } break;}case 1: { const { n } = current; $return(n * $result); // 这里是拿到子递归的返回值并返回这次递归的后果。 break;}因为要模仿函数调用的过程，等到有返回值后能力再执行前面的代码，所以必须要这样拆分才行。同时还要留神的是，因为是用 while 循环来改写递归，所以当波及一些语法糖或者 for..in 这种循环的时候，必须要改写为对应的 while 循环代码才行。
上面再来看一个简单点的例子，对象深拷贝递归函数：
// JS 对象深拷贝，简略实现。function deepCopy(obj, map = new Map()) { if (typeof obj === 'object') { let res = Array.isArray(obj) ? [] : {}; if (map.has(obj)) { return map.get(obj); } map.set(obj, res); for (const key in obj) { if (obj.hasOwnProperty(key)) { res[key] = deepCopy(obj[key], map); } } return map.get(obj); } else { return obj; }}function deepCopy2(obj, map = new Map()) { const $stack = []; let $result = {}; const $call = (obj, map) => { $stack.push({ continuation: 0, obj, map, res: null, keys: [], key: '' }) }; const $return = obj => { $stack.pop(); $result = obj; }; $call(obj, map); while ($stack.length > 0) { const current = $stack[$stack.length - 1]; switch (current.continuation) { case 0: { const { obj, map } = current; if (typeof obj === 'object') { current.res = Array.isArray(obj) ? [] : {}; if (map.has(obj)) { $return(map.get(obj)); break; } current.continuation = 1; break; } else { $return(obj); break; } } case 1: { const { obj, map, res } = current; map.set(obj, res); for (const key in obj) { if (obj.hasOwnProperty(key)) { current.keys.push(key); } } current.continuation = 2; break; } case 2: { if (current.keys.length > 0) { current.key = current.keys.shift(); const { obj, map, key } = current; $call(obj[key], map); current.continuation = 3; break; } else { $return(map.get(current.obj)); break; } } case 3: { current.res[current.key] = $result; current.continuation = 2; break; } } } return $result;}这个例子就呈现了 for..in 这种循环，所以必须要先变成 while 循环能够解决的形式；还有一点要留神的是 res[key] = deepCopy(obj[key], map); 这句代码中调用了递归，那么 key 也在须要保留的上下文变量中。
总结
实践上所有的递归函数都能够用以上的模板套路改写为非递归模式。但我感觉这种形式其实没有多大的实用性，实质上也是模仿了函数调用栈的实现，而且这种改写会使代码更新简单和难以了解。但另一方面，我感觉了解和学习这种改写形式还是有价值的，能够加深函数调用栈和计算机怎么运行代码管制的了解，还是有点意思的。
欢送 star 和关注我的 JS 博客：小声比比 JavaScript