从一个走台阶故事说起

在初学编程 递归 的概念的时候，教材上或教师或许都介绍过 斐波那契数列。笔者第一次接触是在高二阶段一堂计算机课程在老师的指导下使用 VB 语言递归的方式实现了这个兔子繁殖的游戏统计函数。后来步入职场，经历过两次面试都涉及到走台阶的故事——有一道很长很长的台阶，你一步能跨越一步或两步，那到达某个位置的台阶你有多少种走法？

聪明的你通过简单的 数学归纳：

1个台阶：1种。
2个台阶：2种——连续走2次1步，或1次2步。
3个台阶：3种——连续走3次1步，或1次2步再1次1步，或1次1步再1次2步。
4个台阶：5种——连续走4次1步，或1次1步再1次2步再1次1步，或2次1步再1次2步，或1次2步在2次1步，或2次2步。
5个台阶：8种。
6个台阶：13种。
...

找到规律后一定知道这是兔子繁殖游戏的另一种演绎——依旧是 斐波那契数列 $f(n)=f(n-1)+f(n-2)$。

本篇文章针对 $f(n)=f(n-1)+f(n-2)$ 的编程实现梳理下实际开发落地过程中会面临的一些讨论。

递归

首先最容易给出的解法是 递归。但这种情况下面试官会引导（或直接指出）这种实现方式的空间复杂度是 $O(n)$，时间复杂度是$O(2^n)$，并非是性能最佳实践——特别是时间复杂度是指数级别的增长。

function fibonacci(n) {
  if (n <= 1) {
    return n
  }
  return fibonacci(n - 1) + fibonacci(n - 2)
}

info

随着 n 的增大，递归树的节点数会呈指数级增长，导致大量的重复计算，时间复杂度为$O(2^n)$。同时，系统栈需要保存每一层递归调用的上下文信息，空间复杂度为$O(n)$。

尾递归

确实，时间复杂度是$O(2^n)$。造成时间复杂度如此之高的主要因素是在递归中会出现重复计算，比如在计算 $f(n+1)$、$f(n+2)$ 都会重复计算 $f(n)$、$f(n-2)$、$f(n-2)$，这种重复计算的增长是指数级别的。

为规避这类重复计算可以通过尾递归的方式优化——在一个递归函数里，递归调用语句是该函数体的最后一个操作，并且这个递归调用的返回值会直接作为整个函数的返回值。

function fibonacci(n, prev = 0, next = 1) {
  if (n === 0) {
    return prev
  }
  return fibonacci(n - 1, next, prev + next)
}

在新的实现中，引入了两个额外的参数 prev 和 next 来保存中间结果。prev 初始化为 $f(0)=0$，next 初始化为 $f(1)=1$。
在每次递归调用时，会将问题规模 n 减 1，同时更新 prev 和 next 的值。具体来说，新的 prev 等于原来的 next，新的 next 等于原来的 prev + next。
递归调用 fibonacci(n - 1, next, prev + next) 是函数的最后一个操作，其返回值会直接作为整个函数的返回值，不需要在递归返回后进行额外的计算。

以计算 fibonacci(5, 0, 1) 为例，递归过程如下：

• 第一次调用：fibonacci(5, 0, 1) 会递归调用 fibonacci(4, 1, 1)。
• 第二次调用：fibonacci(4, 1, 1) 会递归调用 fibonacci(3, 1, 2)。
• 第三次调用：fibonacci(3, 1, 2) 会递归调用 fibonacci(2, 2, 3)。
• 第四次调用：fibonacci(2, 2, 3) 会递归调用 fibonacci(1, 3, 5)。
• 第五次调用：fibonacci(1, 3, 5)，此时 n 为 1，返回 next 值为5，即 $f(5)$ 的结果。

因此使用 尾递归 实现的 斐波那契数列 时间复杂度为$O(n)$——因为只需要进行n次递归调用——效率远远优于普通递归方式的$O(2^n)$。

通常情况下，一门编程语言的每一次函数调用都会创建一个函数上下文环境（需要在编译器栈中存储大量的函数调用上下文信息），但一些编程语言的编译器可以针对 尾递归 优化规避这些上下文信息的重复存储，从而也能将空间复杂度降低到$O(1)$。

空间换时间

尾递归确实是个好的优化思路，只要进行简单的调用方式改造就能将时间复杂度为优化到$O(n)$。

const fibonacci = (function () {
  const cache = {}

  return function fib(n) {
    if (n in cache) return cache[n]
    return (cache[n] = n === 0 || n === 1 ? n : fib(n - 1) + fib(n - 2))
  }
})()
console.log(fibonacci(10))

const fibonacci = (function () {
  const cache = {}

  return function fib(n, prev = 0, next = 1) {
    if (n in cache) return cache[n]
    return (cache[n] = n === 0 ? prev : fib(n - 1, next, prev + next))
  }
})()
console.log(fibonacci(10))

通项式

通项式推导方式一：数列思路

通项式推导方式一：矩阵思路