将循环转换为递归：模板和尾递归解释

聖光之護

发布时间：2024-12-14 12:45:02

536人浏览过

来源于dev.to

转载

将循环转换为递归：模板和尾递归解释

递归和循环都是在编程中实现重复任务的基本工具。虽然 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：对数组求和

使用循环：

PaperFake

AI写论文

下载

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

  // additional computation occurs
  // after the recursive call returns
  return n * factorial(n - 1); // recursive case
}

尾递归的好处

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

尾递归模板

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

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

尾递归模板

function tailrecursivefunction(iterationstate, dataoraccumulator) {
  // base case: stop when the iteration state satisfies the condition
  if (basecondition(iterationstate)) {
    return dataoraccumulator; // final result
  }

  // recursive case: update state and accumulator
  return tailrecursivefunction(
    updateiterationstate(iterationstate),
    updateaccumulator(dataoraccumulator, iterationstate)
  );
}

尾递归示例

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

function sumarraytailrecursive(index, arr, accumulator = 0) {
  if (index >= arr.length) return accumulator; // base case
  return sumarraytailrecursive(index + 1, arr, accumulator + arr[index]); // tail-recursive call
}

console.log(sumarraytailrecursive(0, [1, 2, 3, 4])); // output: 10

示例 2：尾递归阶乘

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

console.log(factorialTailRecursive(5)); // Output: 120