斐波那契-简单
难度：简单
题目描述：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ...
找出规律
解题思路：
递归法：
function fibonacci(n) {
if (n === 0 || n === 1) {
return n;
}
console.log(`fibonacci(${n - 1}) + fibonacci(${n - 2})`);
return fibonacci(n - 2) + fibonacci(n - 1);
}
1
2
3
4
5
6
7
2
3
4
5
6
7
数组缓存
let fibonacci = (function () {
let temp = [0, 1];
return function (n) {
let result = temp[n];
if (typeof result != "number") {
result = fibonacci(n - 1) + fibonacci(n - 2);
temp[n] = result; // 将每次 fibonacci(n) 的值都缓存下来
}
return result;
};
})(); // 外层立即执行
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
递推法： ```javascript function fibonacci(n) { let current = 0; let next = 1; let temp; for(let i = 0; i < n; i++) { temp = current; current = next; next += temp; } console.log(`fibonacci(${n}, ${next}, ${current + next})`); return current; } 写法二； function fib(n) { let current = 0; let next = 1; for(let i = 0; i < n; i++) { [current, next] = [next, current + next]; } return current; } ```
尾调用优化
function fib(n, current = 0, next = 1) {
if (n == 0) return 0;
if (n == 1) return next; // return next
console.log(`fibonacci(${n}, ${next}, ${current + next})`);
return fib(n - 1, next, current + next);
}
1
2
3
4
5
6
2
3
4
5
6