理解遞歸
要理解遞歸, 首先要理解遞歸 --佚名
遞歸是一種解決問題的方法, 他從解決問題的各個(gè)小部分開始, 知道解決最初的大問題. 遞歸通常涉及函數(shù)調(diào)用自身
// 能夠直接調(diào)用自身的方法或函數(shù)
function recursiveFunction(someParam) {
recursiveFunction(someParams);
}
// 間接調(diào)用自身的函數(shù)
function recursiveFunction1(someParam) {
recursiveFunction2(someParam);
}
function recursiveFunction2(someParam) {
recursiveFunction1(someParam);
}
上面的兩個(gè)示例如果執(zhí)行會(huì)一直調(diào)用下去, 因此, 每個(gè)遞歸都必須有基線條件, 一個(gè)不再遞歸調(diào)用的條件（停止點(diǎn)）, 以防止無(wú)限遞歸
計(jì)算一個(gè)數(shù)的階乘
數(shù) n 的階乘荐开，定義為 n!供炎，表示從 1 到 n 的整數(shù)的乘積, 5 的階乘表示為 5!，和 5 × 4 × 3 × 2 × 1 相等，結(jié)果是 120
- 迭代階乘
const factorialIterative = (number) => {
if (number < 0) return undefined;
let total = 1;
for (let n = number; n > 1; n--) {
total = total * n;
}
return total;
};
console.log("factorialIterative(5)", factorialIterative(5)); // 120
- 遞歸階乘
- 5 的階乘
5*4*3*2*1 - f(5) = 5 _ f(4): 我們可以用 5 _ 4! 來(lái)計(jì)算 5!
- f(5) = 5 _ (4 _ f(3)): 需要計(jì)算 4!, 可以用 4 * 3!
- f(5) = 5 _ 4 _ (3 * f(2))
- f(5) = 5 _ 4 _ 3 _ (2 _ f(1))
- f(5) = 5 _ 4 _ 3 _ 2 _ (1)
- f(1)或 f(0) 返回 1, 1! = 1
- 5 的階乘
const factorial = (n) => {
if (n === 1 || n === 0) return 1; // 基線條件
return n * factorial(n - 1);
};
console.log("factorial(5)", factorial(5));
調(diào)用棧
- JavaScript 調(diào)用棧大小的限制
如果忘記加上用以停止函數(shù)遞歸調(diào)用的基線條件左胞，會(huì)發(fā)生什么呢？遞歸并不會(huì)無(wú)限地執(zhí)行下去乔煞，瀏覽器會(huì)拋出錯(cuò)誤啸罢，也就是所謂的棧溢出錯(cuò)誤 （stack overflow error）
斐波那契數(shù)列
斐波那契數(shù)列是另一個(gè)可以用遞歸解決的問題。它是一個(gè)由 0加勤、1仙辟、1同波、2、3叠国、5未檩、8、13粟焊、21冤狡、34 等數(shù)組成的序列。數(shù) 2 由 1 + 1 得到项棠，數(shù) 3 由 1 + 2 得到悲雳，數(shù) 5 由 2 + 3 得到，以此類推
- 位置 0 的 斐波那契數(shù)是零
- 1 和 2 的斐波那契數(shù)是 1
- n (此處 n > 2)的斐波那契數(shù)是(n - 1) 的斐波那契數(shù)加上(n - 2)的斐波那契數(shù)
- 迭代求斐波那契數(shù)
const fibonacciIterative = (n) => {
if (n < 1) return 0;
if (n <= 2) return 1;
let fibNMinus2 = 0;
let fibNMinus1 = 1;
let fibN = n;
for (let i = 2; i <= n; i++) {
// n >= 2
fibN = fibNMinus1 + fibNMinus2; // f(n-1) + f(n-2)
fibNMinus2 = fibNMinus1;
fibNMinus1 = fibN;
}
return fibN;
};
console.log("fibonacciIterative(10)", fibonacciIterative(10)); // 55
- 遞歸求斐波那契數(shù)
const fibonacci = (n) => {
if (n < 1) return 0;
if (n <= 2) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
};
console.log("fibonacciIterative(10)", fibonacciIterative(10)); // 55
斐波那契
- 記憶化斐波那契數(shù)
記憶化是一種保存前一個(gè)結(jié)果的值的優(yōu)化技術(shù)香追，類似于緩存, 在上圖中, 我們可以看到 f(3) 被計(jì)算了兩次
// 聲明了一個(gè) memo 數(shù)組來(lái)緩存所有的計(jì)算結(jié)果
const fibonacci = ((memory = [0, 1]) => {
return function fib(n) {
let result = memory[n];
if (typeof result !== "number") {
result = fib(n - 1) + fib(n - 2);
memory[n] = result;
}
return result;
};
})();
console.log("fibonacci(10)", fibonacci(10));
