背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

动态规划

不必要的递归调用

下面是一个寻找数组中最大值的递归函数。

def max(array)
  # 基准情形——如果数组中只有一个元素，那么根据定义，它就是最大值：
  return array[0] if array.length == 1
  # 把第一个元素和数组剩余元素中的最大值做比较。如果第一个元素更大，那么就把它作为最大值返回：
  if array[0] > max(array[1, array.length - 1])
    return array[0]
  # 否则就返回剩余元素中的最大值：
  else
    return max(array[1, array.length - 1])
  end
end

这个函数递归调用的本质在于把一个数（array[0]）和数组剩余元素中的最大值做比较。（因为要计算数组剩余元素中的最大值，需要调用max函数，所以它是递归函数。）

我们用条件语句进行比较。条件语句的前半部分如下所示。

if array[0] > max(array[1, array.length - 1])
    return array[0]

以上代码的意思是：如果这个数（array[0]）比数组剩余元素中的最大值（max(array[1, array.length - 1])）还要大，那么array[0]就是数组的最大值，可以作为结果返回。

条件语句的后半部分如下所示：

else
  return max(array[1, array.length - 1])

以上代码的意思是：如果array[0]不大于数组剩余元素中的最大值，那么该最大值也是整个数组的最大值，可以作为结果返回。

虽然这段代码是正确的，但它的效率比较低。如果仔细观察，你会发现max(array[1,array.length - 1])在条件语句的前后两个部分各出现了一次。

问题在于，每次调用max(array[1, array.length - 1])都触发了一系列的递归调用。

下面以[1, 2, 3, 4]为例进行分析。

首先我们会把1和剩余数组[2, 3, 4]的最大值进行比较。这会触发2和[3, 4]的最大值的比较，继而又会触发3和[4]的比较。最后这次比较还会触发一次递归调用，也就是基准情形。不过，要真正看清代码的运行，需要从最“底端”的调用开始，沿着调用链向上分析。

最长递归链分析

调用max([4])时，函数会直接返回4。这是因为下面这行代码决定了基准情形就是只有一个元素的数组。

return array[0] if array.length == 1

这很简单——只是一次普通的函数调用。

沿着调用链向上，看看调用max([3, 4])时会发生什么。在条件语句的前半部分（if array[0] > max(array[1, array.length - 1])）中，我们比较了3和max([4])。但调用max([4])是一次递归调用。

这一步完成之后，代码现在就可以把3和max([4])的结果进行比较了。因为3不大于这个结果（4），所以会触发条件语句的后半部分。（也就是return max(array[1,array.length - 1])。）在这种情况下，我们会返回max([4])。

但是在返回max([4])时，还会调用一次max([4])。这是第二次触发max([4])的调用。

如你所见，max([3, 4])最后调用了max([4])两次。当然，我们希望避免不必要的事。假如已经计算过了max([4])的结果，那么为什么还要再调用一次同样的函数，得到相同的结果呢？

问题就出在这里：这还只是max([2, 3, 4])条件语句的前半部分。在后半部分，还会再次调用max([3, 4])。

因此，max([1, 2, 3, 4])最后会调用max函数15次。

我们确实需要部分递归调用，但肯定不是全部。例如，我们肯定需要计算max([4])，但是只要调用一次就能得到它的结果了。而在上面的代码中，它被调用了8次。

大O小改

幸运的是，有一种简单的方法可以避免多余的递归调用。代码只会调用max一次，然后把结果存储在一个变量中。

def max(array)
  return array[0] if array.length == 1
  # 计算剩余数中的最大值并存储在变量中：
  max_of_remainder = max(array[1, array.length - 1])
  # 把第一个数和这个变量进行比较：
  if array[0] > max_of_remainder
    return array[0]
  else
    return max_of_remainder
  end
end

这个简单的修改把调用max的次数减少到了4次。可以加入puts "RECURSION"，自己试着运行一下代码。

这里的诀窍在于：每个必要的递归调用只进行一次，然后把结果存储在变量中，这样就无须重复调用了。

递归的效率

每次数据量增加1，算法所需步数差不多都要翻番。这是O(2^N)算法的特征，它也是一种非常慢的算法。

然而，在修改之后，数组中有多少元素，max函数就会调用自己多少次。这意味着它的效率是O(N)。

牢记一点：避免多余的递归调用是快速递归的关键。把计算结果存储在变量中这种修改乍一看可能很不起眼，但它能把函数的速度从O(2^N)提高到O(N)。

总结

递归确实能解决一些问题，但如果使用不当，它也会带来一些新问题。事实上，递归通常是O(2^N)这种缓慢算法背后的“罪魁祸首”。

但好消息是，许多问题是可以避免的。阅读本文，你会学习如何发现递归代码中最常见的速度问题，以及如何用大O记法表示这些算法的复杂度。更重要的是，你会学习解决这些问题的技巧。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。