背景

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

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

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

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

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

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

学习编写递归代码

递归类别：重复执行

一旦学会了解决一类问题的有效方法，就可以用这种方法去解决其他的同类问题。

最简单的一类，就是那些目标为重复执行一项任务的算法。

下面来看看“重复执行”类别下的另一个问题。我们这次要写一个算法，把一个数组中的每一个数都翻倍。注意，不是创建一个新数组，而是原地修改数组。

这个算法依然会重复执行同一项任务。具体来说就是把数翻倍。先翻倍第一个数，然后是第二个，以此类推。

再来看看原地修改的概念，以防你还不了解它。

通常来说，操作数据有两种基本方法。下面以翻倍数组中的值为例。假如有一个数组[1,2, 3, 4, 5]，我们想把它“翻倍”成数组[2, 4, 6, 8, 10]。以下是两种做法。

第一种做法是创建一个新数组来存储“翻倍后”的数据，不修改原有数组。其代码如下所示。

a = [1, 2, 3, 4, 5]
b = double_array(a)

因为double_array函数创建并返回了一个新数组，所以检查a和b的值就会看到如下情形。

a # [1, 2, 3, 4, 5]
b # [2, 4, 6, 8, 10]

原来的数组a没有变化，b则表示新数组。

第二种做法叫作“原地”修改。函数会修改传进来的原始数组。

使用原地修改的话，a和b就会变成下面这样。

a # [2, 4, 6, 8, 10]
b # [2, 4, 6, 8, 10]

原地函数会直接修改a。而b只是指向a所在的同一个数组。

可以根据项目的需要选择其中一种做法。

下面试试在Python中编写这个double_array()函数。因为我们知道最后一行会是递归调用，所以先把它加进来。

def double_array(array):
  double_array(array)

现在索引0处的数翻倍了，该如何继续操作索引1处的数呢？

假如使用循环，那么就需要用一个变量来记录索引并不断增加1，就像下面这样。

def double_array(array):
  index = 0
  while (index < len(array)):
    array[index] *= 2
    index += 1

而在递归版本中，函数唯一的参数就是数组。我们需要某种记录并递增索引的方法。该怎么做呢？

这就是我们要介绍的下一个技巧——传入额外参数。

修改函数的开头，让它接受两个参数：函数本身和记录用的索引。

def double_array(array, index):

这样，在调用函数时就需要传入数组本身和开始的索引，也就是0。

double_array([1, 2, 3, 4, 5], 0)

把索引也作为参数后，就有了在递归调用时递增并记录索引的方法。代码如下所示。

def double_array(array, index):
  array[index] *= 2
  double_array(array, index + 1)

后续的每次递归调用都需要再次传入数组作为第一个参数，同时传入一个递增的索引。这让我们可以像使用循环那样跟踪记录索引。

不过代码还没完成。在索引超过数组末尾后，函数会试图乘一个不存在的数，这就产生了错误。为此，还需要一个基准情形。[插图]可以用下列代码测试这个函数。

def double_array(array, index):
  # 基准情形：索引超过数组末尾
  if index >= len(array):
    return
  array[index] *= 2
  double_array(array, index + 1)

可以用下列代码测试这个函数。

array = [1, 2, 3, 4]
double_array(array, 0)
print(array)

现在需要像下面这样调用函数。

double_array([1, 2, 3, 4, 5], 0)

递归类别：计算

递归擅长解决有任意多层深度的问题。而递归擅长的另一个领域是能根据问题的子问题进行计算的情景。

要编写函数来计算阶乘，可以使用循环从1开始计算。换言之，可以用1乘以2，再把结果乘以3，乘以4，直到乘以6。使用循环的Ruby实现如下。

def factorial(n)
  product = 1
  (1..n).each do |num|
    product *= num
  end
  return product
end

不过，还可以用不同的方法来解决该问题，也就是基于子问题来计算阶乘。子问题和原问题相同，只不过输入更小。

下面以阶乘为例进行说明。

仔细想一下，你会发现factorial(6)其实就是6乘以factorial(5)的结果。这是因为factorial(6)是6 × 5 × 4 × 3 × 2 × 1。而factorial(5)是5 × 4 × 3 × 2 × 1。因此factorial(6)就等价于6 × factorial(5)。只要得到了factorial(5)的结果，就可以把它乘以6，从而得到factorial(6)的答案。因为factorial(5)的问题更小，并且可以用来计算一个更大的问题，所以我们说factorial(5)是factorial(6)的子问题。

实现如下：

def factorial(number)
  if number == 1
    return 1
  else
    return number * factorial(number - 1)
  end
end

总结

学习编写递归函数，掌握了让这个学习过程更简单的窍门和技巧，但是还需要练习。

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