从一个走台阶故事说起

在初学编程 递归 的概念的时候,教材上或教师或许都介绍过 斐波那契数列。笔者第一次接触是在高二阶段一堂计算机课程在老师的指导下使用 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种。
...
找到规律后一定知道这是兔子繁殖游戏的另一种演绎——依旧是 斐波那契数列 。
本篇文章针对 的编程实现梳理下实际开发落地过程中会面临的一些讨论。
递归
首先最容易给出的解法是 递归。但这种情况下面试官会引导(或直接指出)这种实现方式的空间复杂度是 ,时间复杂度是,并非是性能最佳实践——特别是时间复杂度是指数级别的增长。
function fibonacci(n) {
if (n <= 1) {
return n
}
return fibonacci(n - 1) + fibonacci(n - 2)
}
随着 n
的增大,递归树的节点数会呈指数级增长,导致大量的重复计算,时间复杂度为。同时,系统 栈需要保存每一层递归调用的上下文信息,空间复杂度为。
尾递归
确实,时间复杂度是。造成时间复杂度如此之高的主要因素是在递归中会出现重复计算,比如在计算 、 都会重复计算 、、,这种重复计算的增长是指数级别的。
为规避这类重复计算可以通过尾递归的方式优化——在一个递归函数里,递归调用语句是该函数体的最后一个操作,并且这个递归调用的返回值会直接作为整个函数的返回值。
function fibonacci(n, prev = 0, next = 1) {
if (n === 0) {
return prev
}
return fibonacci(n - 1, next, prev + next)
}
在新的实现中,引入了两个额外的参数 prev
和 next
来保存中间结果。prev
初始化为 ,next
初始化为 。
在每次递归调用时,会将问题规模 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,即 的结果。
因此使用 尾递归 实现的 斐波那契数列 时间复杂度为——因为只需要进行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))