尾递归

函数在尾部调用自身就成为尾递归

function factorial(n) {
  if (n === 1) return n;
  return n * factorial(n - 1);
}
// 计算n的阶乘，最多需要保存n个调用记录，复杂度为O(n)
console.time(1);
console.log(factorial(5)); // 120
console.timeEnd(1); // 1: 1.60400390625ms

// 如果改为尾递归，只需要保留一个调用记录，复杂度为O(1)
function factorial01(n, tntal) {
  if (n === 1) return tntal;
  return factorial(n - 1, n * tntal);
}
console.time(2);
console.log(factorial01(5, 1)); // 120
console.timeEnd(2); // 2: 0.14404296875ms

Fibonacci（斐波那契）数列

function fibonacci(n) {
  if (n === 0) return 1;
  if (n === 1) return 1;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

1. 迭代法

function fibonacciIterative(n) {
  let a = 0;
  let b = 1;
  for (let i = 2; i <= n; i++) {
    const temp = a + b;
    a = b;
    b = temp;
  }
  return b;
}

1. 尾递归

function fibonacciTailRecursive(n, a = 0, b = 1) {
  if (n === 0) return a;
  if (n === 1) return b;
  return fibonacciTailRecursive(n - 1, b, a + b);
}

1. 动态规划

function fibonacciDynamic(n) {
  const fib = [0, 1];
  for (let i = 2; i <= n; i++) {
    fib[i] = fib[i - 1] + fib[i - 2];
  }
  return fib[n];
}

柯里化（currying）

function factorial(n, total = 1) {
  if (n === 1) return total;
  return factorial(n - 1, n * total);
}

factorial(5); // 120

动态规划

function fibonacci(n) {
  let result = [0, 1];
  if (n <= 1) return result[n];
  for (let i = 2; i <= n; i++) {
    result[i] = result[i - 2] + result[i - 1];
  }
  return result[n];
}
console.log('fibonacci', fibonacci(10));