Skip to main content

从一个走台阶故事说起

在初学编程 递归 的概念的时候,教材上或教师或许都介绍过 斐波那契数列。笔者第一次接触是在高二阶段一堂计算机课程在老师的指导下使用 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(n1)+f(n2)f(n)=f(n-1)+f(n-2)

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

递归

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

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

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

尾递归

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

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

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

在新的实现中,引入了两个额外的参数 prevnext 来保存中间结果。prev 初始化为 f(0)=0f(0)=0next 初始化为 f(1)=1f(1)=1
在每次递归调用时,会将问题规模 n 减 1,同时更新 prevnext 的值。具体来说,新的 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)f(5) 的结果。

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

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

空间换时间

尾递归确实是个好的优化思路,只要进行简单的调用方式改造就能将时间复杂度为优化到O(n)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))

通项式

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

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