面试官：递归是个什么东东？

面试官：递归是个什么东东？

今天的主题本来是两个：

• 递归
• 堆栈 但是由于篇幅太长，我们分为两部分进行，今天先来讲讲递归，我们平常可能会用到递归，简单来说就是自己调用自己，例如，我们的递归组件，递归函数求和，等等。但是我们从来没有仔细研究下这递归到底有什么优缺点？

本文你应该带着两个问题进行阅读

• 什么是递归
• 如何使用递归

什么是递归

递归是一种编程模式，在一种任务可以自然地拆分为相同类型的多个任务，但更简单的情况下很有用。或者，当一个任务可以简化为一个简单的动作以及该任务的一个更简单的变体时。或者，正如我们将很快看到的那样，处理某些数据结构。

当一个函数解决任务时，在此过程中它可以调用许多其他函数。这种情况的部分情况是函数调用自身时。这就是所谓的递归。

两种思维方式

举个简单的例子，比如我们求 x 的 n 次幂，这个时候我们可能需要用到递归：

pow(2, 2) = 4
pow(2, 3) = 8
pow(2, 4) = 16

第一种，迭代思维

最经常使用就是使用 for 循环：

function pow(x, n) {
  let result = 1;

  // multiply result by x n times in the loop
  for (let i = 0; i < n; i++) {
    result *= x;
  }

  return result;
}

alert( pow(2, 3) ); // 8

第二种，递归思维

function pow(x, n) {
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}

alert( pow(2, 3) ); // 8

值得注意的是，递归变体在本质上是不同的。

当pow(x, n)被调用时，执行分成两个分支：

              if n==1  = x
             /
pow(x, n) =
             \
              else     = x * pow(x, n - 1)

• 如果为n == 1，那么一切都是微不足道的。之所以称为递归基础，是因为它立即产生明显的结果：pow(x, 1)equals x。
• 否则，我们可以表示pow(x, n)为x * pow(x, n - 1)。在数学中，人们会写。这称为递归步骤：我们将任务转换为更简单的动作（乘以）和对同一任务的更简单调用（使用）。接下来的步骤进一步和进一步简化，直到达到 n == 1。

我们也可以说pow 递归调用自己直到n == 1。

例如，要计算pow(2, 4)递归变量，请执行以下步骤：

pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2

因此，递归将函数调用简化为一个更简单的函数调用，然后再简化为一个更简单的函数，依此类推，直到结果变得明显为止。

递归通常较短

递归解通常比迭代解短。

function pow(x, n) {
  return (n == 1) ? x : (x * pow(x, n - 1));
}

嵌套调用（包括第一个）的最大数量称为递归深度。在我们的情况下，它将是n

最大递归深度受JavaScript引擎限制。我们可以依靠它为10000，某些引擎允许更多，但是对于大多数引擎来说100000可能已超出限制。有一些自动优化可以帮助缓解这种情况（“尾部优化”），但是尚无处支持它们，并且仅在简单情况下有效。

那限制了递归的应用，但是它仍然非常广泛。在许多任务中，递归思维方式使代码更简单，更易于维护。

明天我们继续往下讲。