javascript中递归的两种写法

当我们需要重复执行相同的任务时，递归是一种非常有效的解决方案。在JavaScript中，递归有两种主要的写法，分别是普通递归和尾递归。本文将详细讲解这两种递归的写法。

什么是递归

递归是一种编程技巧，它是通过一个函数调用自身来完成某个任务的过程。递归有两个特征：

1. 基线条件：递归过程中，必须有一个基准条件（或称终止条件），它告诉递归函数何时停止执行。
2. 递归条件：递归过程中，必须有一个或多个递归调用，它使我们越来越接近基准条件。

普通递归

普通递归是指递归函数在调用自身之前不进行任何其他操作。普通递归写法简单，但有时会导致性能问题和栈溢出风险。

下面是一个计算阶乘的普通递归示例：

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

console.log(factorial(5)) // 输出 120

在上面的示例中，factorial函数计算n的阶乘。如果n等于0，返回1。否则，返回n乘以factorial(n-1)的结果。

尾递归

尾递归是指递归函数在调用自身之前执行一些操作，这些操作将递归函数的状态作为参数传递给下一次递归调用。尾递归写法可以防止栈溢出和提高性能。

下面是一个计算斐波那契数列的尾递归示例：

function fibonacciHelper(n, prev, next) {
  if (n === 0) {
    return prev;
  } else {
    return fibonacciHelper(n - 1, next, prev + next);
  }
}

function fibonacci(n) {
  return fibonacciHelper(n, 0, 1);
}

console.log(fibonacci(7)) // 输出 13

在上面的示例中，fibonacci函数计算斐波那契数列的第n个数。它调用fibonacciHelper函数来完成计算。fibonacciHelper函数具有三个参数：当前计算的数（n）、上一个数（prev）和下一个数（next）。如果n等于0，则返回上一个数（即所求答案）。否则，递归调用fibonacciHelper函数，并将n减1、next设为prev+next、prev设为next。每次递归调用都将状态作为参数传递，因此不会出现栈溢出的问题。

总结

递归是一种非常有效的解决方案。普通递归简单直接，但可能存在性能和栈溢出风险；而尾递归写法虽然稍微复杂一些，但可以避免栈溢出和提高性能。在使用递归的时候，我们要格外注意基线条件，排除无限递归的情况。