理解递归
要理解递归, 首先要理解递归 --佚名
递归是一种解决问题的方法, 他从解决问题的各个小部分开始, 知道解决最初的大问题. 递归通常涉及函数调用自身
// 能够直接调用自身的方法或函数
function recursiveFunction(someParam) {
recursiveFunction(someParams);
}
// 间接调用自身的函数
function recursiveFunction1(someParam) {
recursiveFunction2(someParam);
}
function recursiveFunction2(someParam) {
recursiveFunction1(someParam);
}
上面的两个示例如果执行会一直调用下去, 因此, 每个递归都必须有基线条件, 一个不再递归调用的条件（停止点）, 以防止无限递归
计算一个数的阶乘
数 n 的阶乘，定义为 n!，表示从 1 到 n 的整数的乘积, 5 的阶乘表示为 5!，和 5 × 4 × 3 × 2 × 1 相等，结果是 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! 来计算 5!
- f(5) = 5 _ (4 _ f(3)): 需要计算 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));
调用栈
- JavaScript 调用栈大小的限制
如果忘记加上用以停止函数递归调用的基线条件，会发生什么呢？递归并不会无限地执行下去，浏览器会抛出错误，也就是所谓的栈溢出错误 （stack overflow error）
斐波那契数列
斐波那契数列是另一个可以用递归解决的问题。它是一个由 0、1、1、2、3、5、8、13、21、34 等数组成的序列。数 2 由 1 + 1 得到，数 3 由 1 + 2 得到，数 5 由 2 + 3 得到，以此类推
- 位置 0 的 斐波那契数是零
- 1 和 2 的斐波那契数是 1
- n (此处 n > 2)的斐波那契数是(n - 1) 的斐波那契数加上(n - 2)的斐波那契数
- 迭代求斐波那契数
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
- 递归求斐波那契数
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
斐波那契
- 记忆化斐波那契数
记忆化是一种保存前一个结果的值的优化技术，类似于缓存, 在上图中, 我们可以看到 f(3) 被计算了两次
// 声明了一个 memo 数组来缓存所有的计算结果
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));
