JavaScript 数据结构与算法 之 递归

递归

递归是一种解决问题的方法，它从解决问题的各个小部分开始，直到解决最初的大问题。递归通常涉及函数调用自身。每个递归函数都必须有基线条件，即一个不再递归调用的条件（停止点），以防止无限递归。

// 直接调用自身函数
function recursiveFunction(someParam) {
  recursiveFunction(someParam);
}

// 间接调用自身函数
function recursiveFunction1(someParam) {
  recursiveFunction2(someParam);
}
function recursiveFunction2(someParam) {
  recursiveFunction1(someParam);
}

// 基线条件
function understandRecursion(doIunderstandRecursion) {
  const recursionAnwser = cofirm('Do you understand recursion?');
  if (recursionAnwser === true) {
    return true;
  }
  understandRecursion(recursionAnwser);
}

计算阶乘

// 迭代阶乘
function factorialIterative(number) {
  if (number < 0) return undefined;
  let total = 1;
  for (let n = number; n > 1; n--) {
    total *= n;
  }
  return total;
}

// 递归
function factorial(n) {
  if (n === 1 || n === 0) {
    return 1;
  }
  return n * factorial(n - 1);
}

斐波那契数列

// 迭代法
function 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;
}

// 递归法
function fibonacci(n) {
  if (n < 1)  return 0;
  if (n <= 2) return 1;
  return fibonacci(n-2) + fibonacci(n-1);
}

// 优化递归
function fibonacciMemoization(n) {
  const memo = [0, 1];
  const fibonacci = (n) => {
    if (memo[n] != null) return memo[n];
    return memo[n] = fibonacci(n - 2, memo) + fibonacci(n - 1, memo);
  }
  return fibonacci(n);
}