递归

函数调用自身的动作,递归用于解决包含较小子问题的难题。递归函数可以接收两个输入:基本情况(结束递归)或递归情况(恢复递归)。

示例

递归函数在满足条件之前会不断地调用自身

以下 Python 代码定义了一个函数,该函数接收一个数字,打印它,然后再次调用自身,并将数字的值减 1。它会一直进行,直到数字等于 0,此时它会停止。

py
def recurse(x):
   if x > 0:
       print(x)
       recurse(x - 1)

recurse(10)

输出将如下所示

10 9 8 7 6 5 4 3 2 1

递归受堆栈大小限制

以下代码定义了一个函数,该函数返回在运行代码的 JavaScript 运行时环境中可用的调用堆栈的最大大小。

js
const getMaxCallStackSize = (i) => {
  try {
    return getMaxCallStackSize(++i);
  } catch {
    return i;
  }
};

console.log(getMaxCallStackSize(0));

常见用法示例

js
const factorial = (n) => {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
};
console.log(factorial(10));
// 3628800
js
const fibonacci = (n) => (n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2));
console.log(fibonacci(10));
// 55
js
const reduce = (fn, acc, [cur, ...rest]) =>
  cur === undefined ? acc : reduce(fn, fn(acc, cur), rest);
console.log(reduce((a, b) => a + b, 0, [1, 2, 3, 4, 5, 6, 7, 8, 9]));
// 45

另请参见