算法——递归技巧
如何编写递归代码❓
递归思想在前端面试中非常常见，除了上面的一些题目之外，二叉树的前中后序遍历，斐波那契数列等都用到了递归的思想。简单地理解递归就是：自己调用自己。那如何编写递归的代码呢
主要有三个关键步骤：
1、明确你这个函数想要干什么
这个函数的功能是什么，他要完成什么样的一件事，而这个，是完全由你自己来定义的。
例如，我定义了一个函数
// 算 n 的阶乘(假设n不为0)
int f(int n){ }
2、找出函数的等价关系式（递归公式）
第三要素就是，我们要不断缩小参数的范围，缩小之后，我们可以通过一些辅助的变量或者操作，使原函数的结果不变。这个等价关系式的寻找，可以说是最难最关键的一步。
例如算n的阶乘：等价关系式：f(n) = n * f(n-1)
3、找到终止条件
所谓递归，就是会在函数内部代码中，调用这个函数本身，所以，我们必须要找出递归的结束条件，不然的话，会一直调用自己，进入无底洞。也就是说，我们需要找出当参数为啥时，递归结束，之后直接把结果返回，请注意，这个时候我们必须能根据这个参数的值，能够直接知道函数的结果是什么。
先来看个简单的例子：
如何求1+2+3+4+...+n的和？相信用for循环的方法大家都知道如何编写：
function sum(n) {
var total = 0
for (int i = 1; i <= n; i++) {
total = total + i
}
return total
}
那如何改为递归的写法呢？
细心观察就会发现，其实就是n与n-1和n-2的关系（等价关系式）
sum(n) = sum(n-1) + n
···
···
···
sum(100) = sum(99) + 100
sum(99) = sum(98) + 99
···
···
···
sum(5) = sum(4) + 5
sum(4) = sum(3) + 4
sum(3) = sum(2) + 3
sum(2) = sum(1) + 2
sum(1) = 1
转化成递归公式就是
function sum(n) {
return sum(n-1) + n
}
第二步：找出终止条件
sum（1）= 1；
结合递归公式和终止条件，1+2+3+4+...+n求和的递归代码如下:
function sum(n) {
if( n ===1 ) return 1
return sum(n-1) + n
}
递归案例
案例1：斐波那契数列
斐波那契数列的是这样一个数列：1、1、2、3、5、8、13、21、34....，即第一项 f(1) = 1,第二项 f(2) = 1.....,第 n 项目为 f(n) = f(n-1) + f(n-2)。求第 n 项的值是多少。
递归函数功能
假设 f(n) 的功能是求第 n 项的值，
递归结束的条件
显然，当 n = 1 或者 n = 2 ,我们可以轻易着知道结果 f(1) =1, f(2) = 1。所以递归结束条件可以为 ‘n <= 2 return 1’。
函数的等价关系式
题目已经把等价关系式给我们了，所以很容易就能够知道 f(n) = f(n-1) + f(n-2)。
最终代码：
int f(int n){
// 1.先写递归结束条件
if(n <= 2){
return n;
}
// 2.接着写等价关系式
return f(n-1) + f(n - 2);
}
案例2： 楼梯问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
递归函数功能
假设 f(n) 的功能是求青蛙跳上一个n级的台阶总共有多少种跳法
函数的等价关系式
每次跳的时候，小青蛙可以跳一个台阶，也可以跳两个台阶，也就是说，每次跳的时候，小青蛙有两种跳法。
第一种跳法：第一次我跳了一个台阶，那么还剩下n-1个台阶还没跳，剩下的n-1个台阶的跳法有f(n-1)种。
第二种跳法：第一次跳了两个台阶，那么还剩下n-2个台阶还没，剩下的n-2个台阶的跳法有f(n-2)种。
所以，小青蛙的全部跳法就是这两种跳法之和了，即 f(n) = f(n-1) + f(n-2)。至此，等价关系式就求出来了。
递归结束的条件
求递归结束的条件，直接把 n 压缩到很小很小就行了，因为 n 越小，我们就越容易直观着算出 f(n) 的多少。
当n=1；f（1）=1，当n=2，f(2)=f(1)+f(0)=2
故if(n <= 1){ return 1; }即可
总代码：
int f(int n){
//f(0) = 0,f(1) = 1，等价于 n<=1时，f(n) = n。
if(n <= 1){
return 1;
}
ruturn f(n-1) + f(n-2);
}
案例3：数组扁平化
如何用递归思想实现数组的扁平化❓即如何把[1, [2], [3, [4, [5]]]]拍平得到[1,2,3,4,5]❓
const flatten = (arr) => {
let result = [];
arr.forEach((item, i, arr) => {
// 若为数组,递归调用 faltten,并将结果与result合并
if (Array.isArray(item)) {
result = result.concat(flatten(item));
} else {//终止条件
result.push(arr[i])
}
})
return result;
};
const arr = [1, [2, [3, 4, 5]]];
console.log(flatten(arr)); // [1, 2, 3, 4, 5]
案例： 快排和递归排序