将循环转换为递归：模板和尾递归解释-js教程-PHP中文网

Converting Loops into Recursion: Templates and Tail Recursion Explained

递归和循环都是在编程中实现重复任务的基本工具。虽然 for 和 while 等循环对于大多数开发人员来说都很直观，但递归提供了一种更抽象、更灵活的解决问题的方法。本文探讨了如何将循环转换为递归函数，提供通用模板，并解释尾递归的概念和优化。

理解递归

什么是递归？

递归是一种函数调用自身来解决同一问题的较小实例的技术。这种自我参照行为会一直持续到满足指定的基本条件为止。

例如，使用递归计算数字的阶乘：

function factorial(n) {
  if (n <= 1) return 1; // Base case
  return n * factorial(n - 1); // Recursive case
}

登录后复制

在此示例中，factorial(n - 1) 通过每次调用减少问题的大小，最终在 n 为 1 时终止。

将循环转换为递归

替换循环的通用模板

要将循环转换为递归，请按照以下步骤操作：

识别迭代状态：确定每次循环迭代期间哪些变量发生变化（例如计数器或索引）。
定义基本情况：指定递归何时停止，类似于循环的退出条件。
执行当前迭代的工作：执行当前循环迭代的逻辑。
递归调用：通过更新迭代状态向基本情况进展。

模板

function recursiveFunction(iterationState, dataOrAccumulator) {
  // Base case: Define when recursion stops
  if (baseCondition(iterationState)) {
    return dataOrAccumulator; // Final result
  }

  // Perform the action for the current iteration
  const updatedData = updateAccumulator(dataOrAccumulator, iterationState);

  // Recursive call with updated state
  return recursiveFunction(updateIterationState(iterationState), updatedData);
}

登录后复制

示例

示例 1：对数组求和

使用循环：

function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

登录后复制

使用递归：

function sumArrayRecursive(arr, index = 0) {
  if (index >= arr.length) return 0; // Base case
  return arr[index] + sumArrayRecursive(arr, index + 1); // Recursive case
}

登录后复制

示例 2：倒计时器

使用循环：

function countdown(n) {
  while (n > 0) {
    console.log(n);
    n--;
  }
}

登录后复制

使用递归：

function countdownRecursive(n) {
  if (n <= 0) return; // Base case
  console.log(n); // Current iteration work
  countdownRecursive(n - 1); // Recursive case
}

登录后复制

理解尾递归

什么是尾递归？

尾递归是递归的一种特殊形式，其中递归调用是函数中的最后一个操作。这意味着递归调用返回后不会发生额外的计算。

尾递归示例：

function factorialTailRecursive(n, accumulator = 1) {
  if (n <= 1) return accumulator; // Base case
  return factorialTailRecursive(n - 1, accumulator * n); // Tail-recursive call
}

登录后复制

非尾递归示例：

function factorial(n) {
  if (n <= 1) return 1; // Base case
  return n * factorial(n - 1); // Recursive case
}

登录后复制

尾递归的好处

堆栈优化：尾递归函数可以通过重用当前堆栈帧来优化，而不是为每次调用创建一个新的堆栈帧。这可以减少内存使用并防止堆栈溢出。
效率：当 JavaScript 引擎支持尾调用优化 (TCO) 时，尾递归可以匹配迭代循环的性能。

尾递归模板

要编写尾递归函数，请遵循以下模式：

将迭代状态放在第一位：迭代状态（例如计数器、索引）应该是第一个参数。
使用累加器：使用附加参数来携带中间结果。
递归调用作为最后一个操作：确保递归调用是函数中的最后一个操作。

尾递归模板

function recursiveFunction(iterationState, dataOrAccumulator) {
  // Base case: Define when recursion stops
  if (baseCondition(iterationState)) {
    return dataOrAccumulator; // Final result
  }

  // Perform the action for the current iteration
  const updatedData = updateAccumulator(dataOrAccumulator, iterationState);

  // Recursive call with updated state
  return recursiveFunction(updateIterationState(iterationState), updatedData);
}

登录后复制

尾递归示例

示例 1：对数组进行尾递归求和

function sumArray(arr) {
  let sum = 0;
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

登录后复制

示例 2：尾递归阶乘

function sumArrayRecursive(arr, index = 0) {
  if (index >= arr.length) return 0; // Base case
  return arr[index] + sumArrayRecursive(arr, index + 1); // Recursive case
}

登录后复制