递归(Recursion)

概念

在wiki中找到如下的一段关于递归的定义

程序调用自身的编程技巧称为递归，递归作为一种算法在程序设计语言中广泛应用

简单的说就是函数自己去调用自己的过程.

理解”递归”

阶乘的例子

function fn(n) = {
  if(n === 1) return 1
  return n * f(n-1)
}

这里我们去找一个数字带入一下，默认下计算的过程，可以拆解成下面这里，先递进 -> 再回归。

上面的过程我们是容易用大脑去模拟挣个步骤，但这往往也是我们去理解递归的一个认知障碍，接下来我们看第二个例子。

走台阶问题

这里有 n 个台阶，每次你可以跨 1 个台阶或者 2 个台阶，请问走这 n 个台阶有多少种走法？

如果我们用大脑直观的去代入：如果有 7 个台阶，你可以 2，2，2，1 这样子上去，也可以 1，2，1，1，2 这样子上去，总之走法有很多，很难穷尽，何况n呢，而且没啥章法，那么用递归我们可以怎么理解呢？

实际上，可以根据第一步的走法把所有走法分为两类，第一类是第一步走了 1 个台阶，另一类是第一步走了 2 个台阶。所以 n 个台阶的走法就等于先走 1 阶后，n-1 个台阶的走法 加上先走 2 阶后，n-2 个台阶的走法。用公式表示就是：f(n) = f(n-1) + f(n-2)
这个是就是递推公式，我们找到它然后再去找临界条件即可。n=1时，f(1) = 1。n=2 时，f(2)=f(1)+f(0)。如果递归终止条件只有一个 f(1)=1，那 f(2) 就无法求解了。所以除了 f(1)=1 这一个递归终止条件外，还要有 f(0)=1，表示走 0 个台阶有一种走法，不过这样子看起来就不符合正常的逻辑思维了。所以，我们可以把 f(2)=2 作为一种终止条件，表示走 2 个台阶，有两种走法，一步走完或者分两步来走

function fn(n: number): number {
  if(n == 1) return 1
  if(n == 2) return 2
  return f(n-1) + f(n+2)
}

总结一下，上面两个写出递归需要满足的3个条件
1、一个问题的解可以分解为一个或者几个子问题的解
上面的例子中，阶乘是分解为了1个子问题，而走台阶时拆分成了2个子问题，暂时记住这个点。

2、这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
这个过程是需要我们去总结出递归的公式关键，其实这里和我们数学中学到的数学归纳法几乎是一样的，只是需要借助代码表示出来，我们之所以有时候难去理解递归的原因之一就是总想去用大脑模拟整个过程，子问题只有一个还好，但是如果多个子问题，比如上面的走台阶就很容易大脑混乱了。这个时候用数学归纳法总结出来，把它抽象成一个递推公式，不用想一层层的调用关系，不要试图用人脑去分解递归的每个步骤。

3、存在递归终止条件
上面终止条件判断还是很重要的，不然就陷入无限循环了，需要找到终止条件的

如何编写递归代码？

有了上面的总结，其实编写递归代码的关键就两步：写出递推公式，找到终止条件，然后将他们用代码编写出来。

递归代码的注意

爆栈

那么为什么会爆栈？

要从递归的实现说起：每一次递归调用都会把函数的局部变量、参数值和返回值等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，这也是递归可以返回上一层的原因。当调用栈过深，达到栈允许最大的深度，就会出现爆栈。

如何解决爆栈？

• 尾递归
• 用迭代代码代替递归代码（非必要不推荐，递归代码更直观）

重复计算

使用递归时还会出现重复计算的问题。刚才我讲的第二个递归代码的例子，如果我们把整个递归过程分解一下的话，那就是这样的

可以直观地看到，想要计算 f(5)，需要先计算 f(4) 和 f(3)，而计算 f(4) 还需要计算 f(3)，因此，f(3) 就被计算了很多次，这就是重复计算问题。我们可以用一个hashMap去缓存计算的值来解决，代码如下

const map = new Map()
function fn(n: number): number {
  if(n == 1) return 1
  if(n == 2) return 2
  // 有缓存就不用再去递归计算
  if(map.has(n)) {
    return map.get(n)
  }
  const res = f(n-1) + f(n+2)
  map.set(n, res)  //缓存res
  return res
}