今天来了解下既爱又恨的 -- 递归
什么是“递归”
给你讲一个故事就明白了，什么故事呢？
从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的是从前有座山，山里有个庙，庙里有个老和尚在给小和尚讲故事，讲的是从前有座山。。。
这就是一个典型的递归，在不考虑岁数等自身的条件下，这将是个死递归，没有终止条件。
再举一个例子。不知道你有没有看过一部号称不怕剧透的电影《盗梦空间》。 小李子团队们每次执行任务的时候，都会进入睡眠模式。如果在梦中任务还完不成的话，就再来个梦中梦，继续去执行任务。如果还不行，就再来一层梦。同样，如果需要回到现实的话，也必须得从最深的那层梦中醒来，然后到第一层梦，然后回到现实中。
递归本质上是将原来的问题，转化为更小的同一问题 大白话就是 一个函数不断的调用自己。
接下来看一个递归的经典例题，就是计算 数列。
指的是这样一个数列：1、1、2、3、5、8、13、21、34、……、x;
代码展示为：
function Fibonacci (n) { if ( n <= 2 ) { return 1}; return Fibonacci(n - 1) + Fibonacci(n - 2);}复制代码 递归三要素
1.一个问题的解可以分解为几个更小的同一题的解
比如说上面的数列，如果要求解第 10 位数是多少 fn(10)，可以分解为求第 9 位数 fn(9) 和第 8 位数 fn(8) 是多少，类似这样分解。
2.分解后的子问题只存在数据不一样的问题。
比如说上面的数列，每次分解后，所形成的子问题求解方式都一样，只是说每次数据规模变了。
3.存在递归终止条件
这个是必须存在的，把问题一层一层的分解下去，但是不能无限循环下去了。 比如说上面的数列，当 n 小于等于 2 的时候，就会停止，此时就已经知道了第一个数和第二个数是多少了，这就是终止条件。不能像老和尚给小和尚讲故事那样，永无止境。
实现递归
首先来分析一个简单的例题，用递归的方式来求解数组中每个元素的和。
根据上面所讲的三要素，来分解下这个问题。
求解数组 arr 的和我们可以分解成是第一个数然后加上剩余数的和，以此类推可以得到如下分解：
const arr = [1,2,3,4,5,6,7,...,n]; sum(arr[0]+...+arr[n]) = arr[0] + sum(arr[1]+...+arr[n]); sum(arr[1]+...+arr[n]) = arr[1] + sum(arr[2]+...+arr[n]); .... sum(arr[n]) = arr[n] + sum([]);复制代码
然后可以推导出一个公式：
x = 0;sum(arr, x) = arr[x] + sum(arr,x+1); // x：表示数组的长度复制代码
再考虑一个终止条件， 当 x 增长到和数组长度一样的时候，就该停止了，而且此时应该返回 0。 所以综上我们可以得出此题的解：
{ function sum(arr) { const total = function(arr, l) { if(l == arr.length) { return 0; } return arr[l] + total(arr, l + 1); } return total(arr, 0); } sum([1,2,3,4,5,6,9,10]);}复制代码 写递归代码的关键就是找到如何将原来的问题转化为更小的同一问题，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件合成最终代码。
注意事项
1.递归容易堆栈溢出
函数调用会使用栈来保存临时变量。每调用一个函数，都会将临时变量封装为栈帧压入内存栈，等函数执行完成返回时，才出栈。而递归非常耗费内存，因为需要同时保存成千上百个调用帧，当数据规模较大的时候很容易发生“栈溢出”错误（stack overflow）。
比如说一个利用递归求阶乘的函数：
function factorial(n) { if (n === 1) return 1; return n * factorial(n - 1);}复制代码 那如何避免这种错误呢？ 我们可以在代码中添加一个参数，记录递归调用的次数。当大于一个数字的时候，手动设置报错信息。比如说上面的例子：
{ let count = 0; function factorial(n) { count ++; if (count > 1000) { console.error('超过了最大调用次数'); return; } if (n === 1) return 1; return n * factorial(n - 1); } factorial(2000)}复制代码 当然这个数字事先无法估算，只适合一些最大深度比较低的递归调用。
2.警惕递归中的重复计算
比如说上文提到的经典数列：
function Fibonacci (n) { if ( n <= 2 ) { return 1}; return Fibonacci(n - 1) + Fibonacci(n - 2);}复制代码 代码很简介，但是却包含了大量的重复计算。
假设要求计算 f(5)f(5) = f(4) + f(3)；于是会递归计算 f(4) 和 f(3)；接着计算 f(4)f(4) = f(3)+ f(2);于是会递归计算f(3)和f(2);复制代码
可以看到，计算 f(5) 和 f(4) 中都要计算 f(3)，但这两次 f(3) 会重复计算，这就是递归的最大问题，对于同一个 f(n)，不能复用。
你好奇过计算一个 f(n) 到底需要有多少次递归调用呢？
我们可以在代码里加一个计数验证一下。
{ let count = 0; function Fibonacci (n) { count ++; if ( n <= 2 ) { return 1}; return Fibonacci(n - 1) + Fibonacci(n - 2); } Fibonacci(n); // n: 要计算的值 console.log(count);}复制代码 实验的结果：
f(5) count = 9f(10) count = 109f(25) count = 150049f(35) count = 18454929f(40) count = 204668309f(45) … 抱歉，我机器太慢，算不出来复制代码
可以把代码在你的机器上试试哦，这看似简单的两句代码的时间复杂度却达到了O的指数级。
为了避免重复计算，可以利用一个对象来保存已经求解过的 f(n)。当递归调用到 f(n) 时，先判断是否求解过了。如果是，则直接从对象中取值返回，不需计算，否则的话，再进行递归，这样就能避免刚讲的问题了。
所以优化后的代码如下：
{ function Fibonacci() { this.obj = {}; this.count = 0; } Fibonacci.prototype.getF = function(n) { this.count ++; if ( n <= 2 ) { return 1}; if (this.obj.hasOwnProperty(n)) { return this.obj[n]; } const ret = this.getF(n - 1) + this.getF(n -2); this.obj[n] = ret; return ret; } var f = new Fibonacci(); f.getF(45);}复制代码 非递归实现
利用递归实现有缺有优，优点是短小精悍；而缺点就是空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多等问题。所以，在选择算法时，要根据实际情况来选择合适的方式来实现。
一般来说，递归可以实现的利用 for 循环都可以实现。比如说上文的数组求和。
接下里我们用 for 循环来改写斐波那契数列。
也比较简单，话不多说，直接行上代码展示：
{ function fibonacci(n) { if (n === 1 || n === 2) { return 1; } let one = 1; let two = 1; let temp = null; for(let i = 3; i <= n; i++) { temp = one + two; // 累加前两个数的和 one = two; two = temp; } return temp; } console.log(fibonacci(40));}复制代码 此代码的时间复杂度应该一眼就能看出来了吧。
总结
刚开始接触 js 的时候，一直都惧怕递归，也很少或者说几乎就不写递归的代码。 但其实学习了以后，发现递归还是挺可爱的。就像在数学找一组数字的规律一样，可以锻炼我们的思维。
比如说 对于刚才用 for 循环改写的斐波那契数列，还有其他解法哦，比如说用数组。
欢迎来讨论哦。
其他优化方式
可以参考阮一峰老师讲的尾递归，链接在下方。
参考文章
有你才完美
自认很菜，创建了一个数据结构和算法的交流群，不限开发语言，前端后端，欢迎各位大佬入驻。