关于斐波那契数列
斐波那契数列 JS 实现
1
2
3
4
5
6
7
8
| // n 默认为大于零的整数
function fib(n) {
if (n < 2) {
return n
} else {
return fib(n - 2) + fib(n - 1)
}
}
|
斐波那契数列函数的实现基本是基于 “递归” 的思想。但是递归会涉及到一个比较严重的问题 “性能”！
性能分析
性能的主要问题是 “调用栈”，当我们递归调用函数的时候，上一个函数始终在执行栈内，无法弹出，导致调用栈不断增加，直到最后一个函数执行完毕，才会一个个一次回归弹出。
优化
优化的点主要在降低压栈次数或者计算次数。
尾递归优化
使用迭代代替递归，即尾递归。主要是在每次函数执行的时候弹出执行栈，返回一个新的函数继续后续执行，使得执行栈中始终只有一个函数。
1
2
3
4
5
6
7
8
9
10
11
| function fib(n) {
if (n < 2) {
return n
} else {
return fib_in(2, n, 1, 0)
}
}
function fib_in(start, end, pre1, pre2) {
return start === end ? pre1 + pre2 : fib_in(start + 1, end, pre1 + pre2, pre1)
}
|
记忆函数
把递归改变成循环，对每次计算的结果进行缓存，避免斐波那契递归过程中大量的重复计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| function fib(n) {
const arr = [0, 1]
for (let i = 0; i < n; i++) {
arr[i + 2] = arr[i + 1] + arr[i]
}
return arr[n]
}
// 或者
function fib(n) {
let pre1 = 0
let pre2 = 1
for (let i = 0; i < n; i++) {
temp = pre2
pre2 = pre1 + pre2
pre1 = temp
}
return pre1
}
|
延伸
我们优化斐波那契函数时，第二种方法是通过缓存结果来避免重复计算。同样的思想在 React 的优化中同样体现，React 的 memo 记忆函数，就是通过缓存相关变量，来避免组件的重复渲染。