算法专题之递归（一）

[timelessover]

定义

程序调用自身的编程技巧称为递归(recursion)。

阶乘

function factorial(n) {
    if (n == 1) return n;
    return n * factorial(n - 1)
}

console.log(factorial(5)) // 5 * 4 * 3 * 2 * 1 = 120

斐波那契数列

function fibonacci(n){
    return n < 2 ? n : fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(5)) // 1 1 2 3 5

递归条件

从这两个例子中，我们可以看出：

构成递归需具备边界条件、递归前进段和递归返回段，当边界条件不满足时，递归前进，当边界条件满足时，递归返回。阶乘中的 n == 1 和 斐波那契数列中的 n < 2 都是边界条件。

总结一下递归的特点：

1. 子问题须与原始问题为同样的事，且更为简单；
2. 不能无限制地调用本身，须有个出口，化简为非递归状况处理。

了解这些特点可以帮助我们更好的编写递归函数。

题目

题目: 求斐波那契数列（兔子数列） 1,1,2,3,5,8,13,21,34,55,89...中的第 n 项

斐波那契数列考察的是递归算法, 但是要注意优化哦, 探寻下面优化前后的代码片段

let count1 = 0
function fn(n) {
  count1++
  if (n === 1 || n === 2) {
    return 1
  }
  return fn(n - 1) + fn(n - 2)
}
console.log(fn(20), count1) // 6765 13529

利用缓存查找进行优化

let count2 = 0
function fn(n) {
  const cache = {}
  function _fn(n) {
    if (cache[n]) {
      return cache[n]
    }
    count2++
    if (n === 1 || n === 2) {
      return 1
    }
    cache[n - 1] = _fn(n - 1)
    cache[n - 2] = _fn(n - 2)
    return cache[n - 1] + cache[n - 2]
  }
  return _fn(n)
}

console.log(fn(20), count2) // 6765 20

通过创建闭包进行缓存数据, 可以看到大大提高了运行性能。