这里所说的通用例程，就是把函数中的递归执行改成循环执行。出于好奇，想找一个通用的递归变非递归的方法，学习一下其中的思想。在网上找了几篇文章，结合对函数调用栈的理解，感觉自己总结的应该比较全面，所以记录下来分享给大家。递归执行和普通嵌套执行的区别我们看一段简单的代码，递归函数计算阶乘：//n!=n*(n-1)*(n-2)*...*1functiongetFactorial(n){如果(n===1){返回1;}else{返回n*getFactorial(n-1);}}递归调用只是意味着函数在执行期间调用自身。如果在下次调用时不满足设置的递归结束条件，则继续这个过程；当递归条件结束时，调用链中的函数将一个一个返回。如上面代码，当n===1时，会触发递归结束条件。这里我们想一想，递归函数的执行和普通函数的嵌套执行有什么区别呢？:thinking:其实没有本质区别。递归调用的层数与普通函数嵌套调用的层数相同。层数由递归结束条件决定。无非就是递归调用自己（直观上就是代码执行回到上一行号）。接下来，当我们的康康函数被嵌套执行时会发生什么。电脑嵌套执行功能如何？如果你了解计算机执行汇编/机器码的原理，你就会知道我接下来可能会讲运行时函数调用栈。但是，我打算用一个简单的描述来引导您了解或加深您的印象。首先我问一个问题：在某个函数执行的过程中，这次执行和另外一次执行有什么不同？简单来说，这个问题可以理解为一个函数执行上下文。此上下文具有以下内容：参数；函数体中定义的变量；返回值；举个函数嵌套执行的例子，当前正在执行函数a，此时有语句执行函数b，此时可以很容易理解为计算机做了以下事情：保存执行上下文功能一；切换到函数b的上下文；代码执行到函数b的开始，函数b执行并返回值；切换回函数a的上下文，继续执行函数a的其余代码；这个过程就是runtime函数调用栈，利用栈的数据结构实现上下文切换。正如我们上面提到的，递归调用可以类比为普通的嵌套调用。无非就是将本次的执行上下文切换到下一次的执行上下文，注意还有代码执行控制（前面说了递归返回上一行执行次数）。通过上面的描述，我们可以得到一些思路，模拟递归，主要解决两个问题：模拟函数调用栈，切换执行上下文；控制语句的执行顺序，从后面的代码返回到前面的代码执行；切换执行上下文，可以用栈来模拟。那么如何控制语句的执行顺序呢？下面介绍一个Continuation技术。继续看例子：functiontest(){console.log(1);控制台日志（2）；console.log(3);}上面输出的是123，我们现在要重新封装一个内容相同的函数，但是改变这三行代码的执行顺序，输出2之后，继续返回1，而当第二次输出2，继续输出3，结束，即输出12123。当然，不需要重复写多余的console.log。计算机通过PC（ProgramCounter）寄存器获取下一条要执行的指令的地址。也就是说，我们需要想办法模拟PC寄存器的工作，看下面的代码：functiontest2(){letcontinuation=0;让计数=0；while(true){switch(continuation){case0:console.log(1);延续=1；休息;案例1：console.log(2)；计数++；延续=计数<2?0：2；休息;案例2：console.log(3)；}上面的方法是使用continuation变量来模拟对PC寄存器的操作。通过根据逻辑改变程序的执行路径，我们可以模拟代码按照我们想要的行数继续执行。下面结合Continuation和模拟栈来康康如何改写递归函数。重写递归函数先来看看例程的模板代码：functionexample(...args){const$stack=[];//模拟栈操作，切换函数上下文。让$结果；//记录每个函数的执行结果。/***调用递归函数，压入新的函数上下文，压入栈操作。*函数的参数和函数中声明的变量必须放入上下文中。*/const$call=(...args)=>{$stack.push({continuation:0,...args});};/***递归函数执行后，切换到上一个函数上下文，Pop操作。*并记录函数的返回值。*/const$return=result=>{$stack.pop();$结果=结果；};//第一次调用。$呼叫（...参数）；while($stack.length>0){constcurrent=$stack[$stack.length-1];switch(current.continuation){//拆分递归函数的代码，使用continuations来控制代码执行。//...}}//返回最后的结果。return$result;}//执行example(...)开始调用“递归”函数。从上面的代码可以看出，模板是利用上面提到的两点来重写递归函数：模拟函数调用栈，切换执行上下文；使用Continuation技术控制语句的执行顺序；然后用这个模板对之前的阶乘递归函数重写后，看起来像这样：//n!=n*(n-1)*(n-2)*...*1functiongetFactorial(n){如果(n===1){返回1;}else{返回n*getFactorial(n-1);}}//改为非递归。函数getFactorial2(n){const$stack=[];让$结果；const$call=n=>{$stack.push({continuation:0,n});};const$return=result=>{$stack.pop();$结果=结果；};$呼叫（n）；while($stack.length>0){constcurrent=$stack[$stack.length-1];switch(current.continuation){case0:{const{n}=current;如果(n===1){$return(1);}else{$call(n-1);当前.继续=1；}休息;}案例1：{const{n}=当前；$return(n*$result);休息;}}}return$result;}这里理解的重点是如何拆分和重写代码。原则上调用递归函数的地方要反汇编。比如原代码是returnn*getFactorial(n-1);，拆分成两部分：case0:{const{n}=current;如果(n===1){$return(1);}else{$call(n-1);//调用递归函数的地方。当前.继续=1；}break;}case1:{const{n}=current;$return(n*$result);//这里是获取子递归的返回值，返回本次递归的结果。break;}因为要模拟调用一个函数的过程，要等到有返回值再执行后面的代码，所以必须这样拆分。同时需要注意的是，由于while循环是用来改写递归的，当涉及到一些语法糖或者for..in循环时，必须改写成对应的while循环代码。再来看一个更复杂的例子，对象深拷贝递归函数：//JS对象深拷贝，简单实现。functiondeepCopy(obj,map=newMap()){if(typeofobj==='object'){letres=Array.isArray(obj)？[]：{}；如果(map.has(obj)){返回map.get(obj);}map.set(obj,res);for(constkeyinobj){if(obj.hasOwnProperty(key)){res[key]=deepCopy(obj[key],map);}}返回map.get(obj);}else{返回对象；}}functiondeepCopy2(obj,map=newMap()){const$stack=[];让$result={};const$call=(obj,map)=>{$stack.push({continuation:0,obj,map,res:null,keys:[],key:''})};const$return=obj=>{$stack.pop();$结果=对象；};$呼叫（对象，地图）；while($stack.length>0){constcurrent=$stack[$stack.length-1];switch(current.continuation){case0:{const{obj,map}=current;if(typeofobj==='object'){current.res=Array.isArray(obj)?[]：{}；我f(map.has(obj)){$return(map.get(obj));休息;}current.continuation=1;休息;}else{$return(obj);休息;}}案例1:{const{obj,map,res}=current;map.set(obj,res);for(constkeyinobj){if(obj.hasOwnProperty(key)){current.keys.push(key);}}current.continuation=2;休息;}案例2:{if(current.keys.length>0){current.key=current.keys.shift();const{obj,map,key}=current;$call(obj[键],地图);当前.继续=3；休息;}else{$return(map.get(current.obj));休息;}}案例3：{current.res[current.key]=$result;当前.继续=2；休息;}}}return$result;}本例中出现了for..in这样的循环，所以首先要改成while循环可以处理的方式；另一件需要注意的事情是res[key]=deepCopy(obj[key],map);这段代码调用了递归，那么key也在需要保存的上下文变量中。理论上，所有递归函数都可以使用上述模板例程重写为非递归形式。但是我觉得这个方法不是很实用。它本质上是模拟了函数调用栈的实现，这种重写会使代码更新变得复杂，难以理解。但另一方面，我认为了解和学习这种重写方法还是很有价值的。加深对函数调用栈的理解，以及计算机如何运行代码控制，很有意思。欢迎star关注我的JS博客：小生笔笔JavaScript
