递归

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

  1. function power(base, exponent) {
  2. if (exponent == 0) {
  3. return 1;
  4. } else {
  5. return base * power(base, exponent - 1);
  6. }
  7. }
  8. console.log(power(2, 3));
  9. // → 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. }
  14. console.log(findSolution(24));
  15. // → (((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)的调用发生。 这个搜索的运气更好 - 它的第一次递归调用,通过另一个递归调用,命中了目标数字。 最内层的调用返回一个字符串,并且中间调用中的每个“||”运算符都会传递该字符串,最终返回解决方案。