今天是系列的第八篇，来晚了。上篇文章还遗留了一个尾递归问题。所以今天想专门写一篇关于递归和尾递归的文章。我们先来了解什么是递归。什么是递归？递归意味着函数调用自身。这是一个非常简单的句子，很容易记住和理解。但是在知道什么是递归之后，我们需要弄清楚如何更好地编写递归函数来解决实际问题。接下来，我们将分两步完成递归函数。第一步：写出递归公式。这一步最重要的一步就是找出这些数据之间的规律，然后把这个规律写成递归公式的形式。举个例子，比如你想用一个函数来实现10*9...5*4*3*2*1的结果，你应该如何实现这个函数呢？现在想想这个数据。我们发现，从当前值*(当前值-1)*(当前值-2)...，假设当前值为n，作为参数传入函数f，那么递归公式是这样的：functionf(n){returnn*f(n-1)}console.log(f(10))但如果函数如上执行，会出现死循环，导致内存溢出。所以我们需要添加一个终止条件来终止这个函数，然后将函数f从执行栈中弹出来释放这个函数中的内存空间。第二步：找出终止条件。最终分析表明，当n===1时，整个计算就终止了。接下来，我们添加这个条件来改进功能。functionf(n){if(n===1){return1}returnn*f(n-1)}console.log(f(10))//3628800让我们再看两个例子来感受递归函数的一些用途。数的累加假设我们要做这样一个操作，即当输入5时，计算5+4+3+2+1，实现一个数累加的结果。我们按照上面的思路来做：第一步写递归公式，即函数fn(n){returnn+fn(n-1)}；第二步，找出终止条件，即当n===1时，不再继续递归，返回1。递归函数可以这样写：functionfn(n){if(n<=1)return1returnn+fn(n-1)}Fibonaccisequencefunctionfib(n){if(n==0||n==1)返回1；returnfib(n-1)+fib(n-2);}上面的序列实现了[1,1,2,3,5,8...]，即f(n)=f(n-1)+f(n-2)这样的关系。但是如果这个值很大，递归调用很深，就会出现栈内存溢出的问题。那么解决堆栈溢出的最佳方案是什么？答案是尾递归。上一篇文章提到递归可能存在几个问题：1.由于递归调用的是函数本身，所以函数调用需要消耗时间和空间：每次调用都要在内存栈中分配空间来存放参数，临时变量，需要时间将数据推入和弹出堆栈，例如返回地址。这势必会导致执行效率大大降低。2.递归中的大部分计算都是重复的。本质是把一个问题分解成多个小问题，它们之间有重叠的部分。这些双重计算也会导致效率下降。3.调用栈可能溢出。堆栈有容量限制。当调用层级过多时，会超出栈的容量限制，导致栈溢出！为了解决上述递归的一些问题，引入了几种解决方法。比如尾递归、循环方法、事件循环方法等。具体内容移步【JS基础系列】彻底了解执行上下文和调用栈（下）。尾递归在这里单独讨论。尾递归尾递归是一种递归解决方案，可以避免不断将函数压入栈中而导致栈溢出。他的技术原理是：函数中返回一个函数后，会删除当前函数在栈中的调用记录，并从调用栈中弹出当前函数的执行上下文。那么如何识别尾递归呢？以下几个例子可以帮助你。尾递归的例子下面我们来看几个例子，分析一下尾递归是一种什么样的情况。测试方法：在safafi浏览器中开启严格模式，可以看到调用栈中执行上下文的push和pop。一般递归可以看到在函数体的断点处会在栈中创建大量的执行上下文，并且不会被销毁（这就是栈溢出的原因）；而尾递归则是在栈中增加函数执行上下文，然后在返回函数时调用函数时，销毁当前函数执行上下文，创建返回函数的执行上下文。所以在尾递归中只有一个活跃的执行上下文。//函数0是尾递归函数a(){constr=c()returnr}//函数1是尾递归函数a(){returnc()}//函数2不是尾递归函数a(){returnc()*20}//函数3不是尾递归函数a(){returnc()||b()}以上是在safari中实际测试判断是否尾递归的结果。总结以上测试的结果：函数2不是尾递归，因为它在调用c()后需要进一步计算。函数3不是尾递归，因为在c()调用之后还有判断动作和对c的可能调用。函数0和函数1是尾递归的，因为它们返回的是一个函数或者一个已经计算好的值，不需要做多余的判断和计算。好的，我知道尾递归是什么样的了。接下来，我们将利用尾递归的知识，对上面的累加递归进行优化。用尾递归修改上面的例子下面是对数组中所有项的累积递归：functionfn(arr,sum=0){if(arr.length===0)returnsumreturnfn(arr.slice(1),arr[0]+sum)}fn([1,2,3,4])直接在浏览器执行，发现还是有很多压栈，貌似没有效果。为什么？我们在Nodejs下开启严格模式，使用--harmony_tailcalls开启尾递归，即：'usestrict'functionfn(arr,sum=0){if(arr.length===0)returnsumreturnfn(arr.slice(1),arr[0]+sum)}fn([1,2,3,4])输入命令：node--harmony_tailcallsfactorial.js我们可以看到每次压栈时，只有一个fn。刚刚看到在标准浏览器中，就像正常的递归一样，有很多执行上下文被推送到调用堆栈上。那是因为浏览器对尾递归的兼容性和优化不够好，所以好像没有变化。但是尾递归也有它自己的一些缺点。例如，尾递归是一种隐式行为。如果代码中存在尾递归调用的死循环，爆栈后开发者很难察觉；栈信息会丢失，调试困难。另外目前各大浏览器厂商对尾递归的支持和兼容性都不是很好。因此，在目前主流浏览器不支持尾递归的情况下，可以对递归的一些重复内容进行优化。重复计算的优化，比如上面的斐波那契数列，会导致大量的fib(3)计算。其实我们可以把这个重复的计算省下来，只计算一次，可以用Map来优化。//原始递归方法functionfib(n){if(n==0||n==1)return1;returnfib(n-1)+fib(n-2);}//优化的递归方法letmapData=newMap()functionfib(n){if(n==0||n==1)return1;if(mapData.get(n)){//这一步避免了重复计算returnmapData.get(n);}letvalue=fib(n-1)+fib(n-2)mapData.set(n,value)returnvalue}fib(20)ok,一些常见的递归例子如：实现深度复制，数组展平等功能。我们将在后面的专题中分析这些常见问题。综上所述，当我们拿到一个函数的时候，首先会分析这个函数是否可以通过递归来实现。写一个好的递归需要两个步骤：（1）写递归公式；(2)寻找终止条件。如果递归层次过深或者数据量过大，都可能造成栈溢出。解决栈溢出的方法一般有尾递归、循环法、事件循环法。尾递归的原理是在递归函数中返回一个函数，栈中当前函数的调用记录会被删除。的执行上下文从执行栈中弹出。还有就是通过Map的数据结构可以省去对同一个值的计算，减少重复计算关键字递归、尾递归、栈溢出。参考资料https://juejin.im/post/59b88e...https://juejin.im/post/5d7df6...https://juejin.im/post/5abb5a...https://blog。csdn.net/tzllxya...https://juejin.im/post/5e09f6...
