递归

一个函数调用自己是完全可以的，只要它没有经常这样做以致溢出栈。 调用自己的函数被称为递归函数。 递归允许一些函数以不同的风格编写。 举个例子，这是power的替代实现：

  1. function power(base, exponent) {
  2.   if (exponent == 0) {
  3.     return 1;
  4.   } else {
  5.     return base * power(base, exponent - 1);
  6.   }
  7. }
  9. console.log(power(2, 3));
  10. // → 8

这与数学家定义幂运算的方式非常接近，并且可以比循环变体将该概念描述得更清楚。 该函数以更小的指数多次调用自己以实现重复的乘法。

但是这个实现有一个问题：在典型的 JavaScript 实现中，它大约比循环版本慢三倍。 通过简单循环来运行，通常比多次调用函数开销低。

速度与优雅的困境是一个有趣的问题。 您可以将其视为人性化和机器友好性之间的权衡。 几乎所有的程序都可以通过更大更复杂的方式加速。 程序员必须达到适当的平衡。

在power函数的情况下，不雅的（循环）版本仍然非常简单易读。 用递归版本替换它没有什么意义。 然而，通常情况下，一个程序处理相当复杂的概念，为了让程序更直接，放弃一些效率是有帮助的。

担心效率可能会令人分心。 这又是另一个让程序设计变复杂的因素，当你做了一件已经很困难的事情时，担心的额外事情可能会瘫痪。

因此，总是先写一些正确且容易理解的东西。 如果您担心速度太慢 - 通常不是这样，因为大多数代码的执行不足以花费大量时间 - 您可以事后进行测量并在必要时进行改进。

递归并不总是循环的低效率替代方法。 递归比循环更容易解决解决一些问题。 这些问题通常是需要探索或处理几个“分支”的问题，每个“分支”可能再次派生为更多的分支。

考虑这个难题：从数字 1 开始，反复加 5 或乘 3，就可以产生无限数量的新数字。 你会如何编写一个函数，给定一个数字，它试图找出产生这个数字的，这种加法和乘法的序列？

例如，数字 13 可以通过先乘 3 然后再加 5 两次来到达，而数字 15 根本无法到达。

使用递归编码的解决方案如下所示：

  1. function findSolution(target) {
  2.   function find(current, history) {
  3.     if (current == target) {
  4.       return history;
  5.     } else if (current > target) {
  6.       return null;
  7.     } else {
  8.       return find(current + 5, `(${history} + 5)`) ||
  9.              find(current * 3, `(${history} * 3)`);
  10.     }
  11.   }
  12.   return find(1, "1");
  13. }
  15. console.log(findSolution(24));
  16. // → (((1 * 3) + 5) * 3)

需要注意的是该程序并不需要找出最短运算序列，只需要找出任何一个满足要求的序列即可。

如果你没有看到它的工作原理，那也没关系。 让我们浏览它，因为它是递归思维的很好的练习。

内层函数find进行实际的递归。 它有两个参数：当前数字和记录我们如何到达这个数字的字符串。 如果找到解决方案，它会返回一个字符串，显示如何到达目标。 如果从这个数字开始找不到解决方案，则返回null。

为此，该函数执行三个操作之一。 如果当前数字是目标数字，则当前历史记录是到达目标的一种方式，因此将其返回。 如果当前的数字大于目标，则进一步探索该分支是没有意义的，因为加法和乘法只会使数字变大，所以它返回null。 最后，如果我们仍然低于目标数字，函数会尝试从当前数字开始的两个可能路径，通过调用它自己两次，一次是加法，一次是乘法。 如果第一次调用返回非null的东西，则返回它。 否则，返回第二个调用，无论它产生字符串还是null。

为了更好地理解函数执行过程，让我们来看一下搜索数字 13 时，find函数的调用情况：

  1. find(1, "1")
  2.   find(6, "(1 + 5)")
  3.     find(11, "((1 + 5) + 5)")
  4.       find(16, "(((1 + 5) + 5) + 5)")
  5.         too big
  6.       find(33, "(((1 + 5) + 5) * 3)")
  7.         too big
  8.     find(18, "((1 + 5) * 3)")
  9.       too big
  10.   find(3, "(1 * 3)")
  11.     find(8, "((1 * 3) + 5)")
  12.       find(13, "(((1 * 3) + 5) + 5)")
  13.         found!

缩进表示调用栈的深度。 第一次调用find时，它首先调用自己来探索以(1 + 5)开始的解决方案。 这一调用将进一步递归，来探索每个后续的解，它产生小于或等于目标数字。 由于它没有找到一个命中目标的解，所以它向第一个调用返回null。 那里的||操作符会使探索(1 * 3)的调用发生。 这个搜索的运气更好 - 它的第一次递归调用，通过另一个递归调用，命中了目标数字。 最内层的调用返回一个字符串，并且中间调用中的每个“||”运算符都会传递该字符串，最终返回解决方案。