数据结构之理解递归

理解递归

要理解递归, 首先要理解递归 --佚名

递归是一种解决问题的方法, 他从解决问题的各个小部分开始, 知道解决最初的大问题. 递归通常涉及函数调用自身

// 能够直接调用自身的方法或函数
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

1. 迭代阶乘

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

2. 递归阶乘
   • 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

const factorial = (n) => {
  if (n === 1 || n === 0) return 1; // 基线条件
  return n * factorial(n - 1);
};

console.log("factorial(5)", factorial(5));

调用栈

3. 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)的斐波那契数

1. 迭代求斐波那契数

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

2. 递归求斐波那契数

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

斐波那契

3. 记忆化斐波那契数

记忆化是一种保存前一个结果的值的优化技术，类似于缓存, 在上图中, 我们可以看到 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));