背景

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

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

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

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

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

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

用递归不停递归

递归函数就是调用自身的函数。只要使用得当，递归就是一个强大的工具。

用递归代替循环

假设需要一个倒数函数。这个函数需要读取一个数字，比如10，然后显示10和0之间的数。

来试试递归。下面是使用递归实现countdown函数的第一次尝试。

function countdown(number) {
  console.log(number);
  countdown(number - 1);
}

我们详细分析一下这段代码。

第1步：调用countdown(10)，这样参数变量的number就会从10开始。

第2步：将number（值为10）打印到命令行中。

第3步：在countdown函数完成之前，因为number – 1是9，所以调用countdown(9)。

第4步：countdown(9)开始执行。在这个函数调用中，将number（值为9）打印到命令行中。

第5步：在countdown(9)完成之前，调用countdown(8)。

第6步：countdown(8)开始执行。将8打印到命令行中。

大部分使用循环的场合能替换为递归。但能使用递归并不代表应该使用递归。递归是写出优雅代码的工具。在前面的例子中，递归并不比for循环优雅或者高效多少。但你很快就会碰到递归真正大显神威的场景。

基准情形

下面继续分析countdown函数的步骤。

为简洁起见，我们跳过一些中间步骤。

第21步：调用countdown(0)。

第22步：将number（也就是0）打印到命令行中。

第23步：调用countdown(-1)。

第24步：将number（也就是（1）打印到命令行中。

糟糕。如你所见，因为我们会打印无穷多的负数，所以这种方案并不完美。

要修正这个算法，需要让算法在倒数到0时停止，不再继续递归。可以加入一个条件语句，确保在number为0时不再继续调用countdown()：

function countdown(number) {
  console.log(number);
  if(number === 0) {
    return;
  } else {
    countdown(number - 1);
  }
}

现在，当number为0时，代码不会再调用countdown()，而是直接返回。这样就不会无限调用下去。

在递归术语中，这种函数不再继续递归的情形称为基准情形。因此0就是countdown()函数的基准情形。每个递归函数都需要至少一个基准情形才能避免无限调用。

阅读递归代码

我们需要时间和练习来习惯递归。你最终会学会两类技能：阅读递归代码和编写递归代码。因为阅读递归代码相对来说更简单，所以先来练习阅读。

从一个例子开始：阶乘计算。

阶乘的定义可以用下面两个例子来描述。

3的阶乘是3 × 2 × 1 = 6。而5的阶乘是5 × 4 × 3 × 2 × 1 = 120。以此类推。

下面是计算阶乘的Ruby递归实现：

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

乍一看这段代码可能让人困惑。要看清它的作用，我推荐以下流程。

(1) 辨认基准情形。

(2) 用基准情形分析代码的步骤。

(3) 找出“倒数第二个”情形。这是基准情形的前一步，稍后你就会明白了。

(4) 用“倒数第二个”情形分析代码的步骤。

(5) 重复这个过程，找出你刚刚分析的情形的前一个情形，并用它分析代码的步骤。

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

可以看出，递归发生在else部分，factorial调用了自身。

else
  return number * factorial(number - 1)
end

因此，基准情形一定是函数没有调用自己的这部分。

if number == 1
  return 1

可以得出结论，number为1即是基准情形。

接下来，假设函数factorial处理的是基准情形factorial(1)，我们来分析其步骤。和它相关的是如下这段代码。

if number == 1
  return 1

这再简单不过了——它是基准情形，不会发生递归。如果我们调用factorial(1)，那么该方法会直接返回1。

文件系统遍历

有一类问题很适合递归：这类问题有很多层，但我们不知道到底有几层。

以遍历文件系统为例。假设你有一个脚本，该脚本可以打印一个目录下的所有子目录的名字。但你不希望脚本只能处理第一级子目录，你希望它能处理子目录下的子目录以及更深层的子目录。

下面写一个简单的Ruby脚本来打印已知目录下的所有子目录的名字：

def find_directories(directory)
  # 检查目录中的每个文件。这些“文件”中有一些可能是子目录
  Dir.foreach(directory) do |filename|
    # 如果当前文件是子目录：
    if File.directory?("#{directory}/#{filename}") &&
    filename != "." && filename != ".."
      # 就打印完整路径：
      puts "#{directory}/#{filename}"
    end
  end
end

可以通过传递目录名来调用这个函数。如果要在当前目录调用，那么可以这样写：

find_directories(".")

在这个脚本中，先检查目录中的所有文件。如果某个文件其实是子目录（并且不是表示当前目录的.和表示上级目录的..），那么就打印其名字。

但这个脚本只能打印一级子目录的名字，而不会打印一级子目录下的子目录的名字。

修改一下脚本，这样它便能多搜索一层：

def find_directories(directory)
  # 循环遍历一级目录：
  Dir.foreach(directory) do |filename|
    if File.directory?("#{directory}/#{filename}") &&
    filename != "." && filename != ".."
      puts "#{directory}/#{filename}"
      # 循环遍历二级子目录：
      Dir.foreach("#{directory}/#{filename}") do |inner_filename|
        if File.directory?("#{directory}/#{filename}/#{inner_filename}") &&
        inner_filename != "." && inner_filename != ".."
          puts "#{directory}/#{filename}/#{inner_filename}"
        end
      end
    end
  end
end

现在，脚本每发现一个目录，都会执行一个相同的循环，搜索这个目录的子目录下的子目录，并打印它们的名字。但这个脚本同样有局限性，它只能搜索2层。如果有3层、4层甚至5层目录怎么办？只能用5层嵌套循环。

如果想穷尽所有层次呢？这听起来不太可能，因为我们根本不知道究竟有多少层。

而此时就是递归出场的时候了。我们可以用递归写一个搜索任意层的简单脚本。

def find_directories(directory)
  Dir.foreach(directory) do |filename|
    if File.directory?("#{directory}/#{filename}") &&
    filename != "." && filename != ".."
      puts "#{directory}/#{filename}"
      # 用子目录递归调用这个函数：
      find_directories("#{directory}/#{filename}")
    end
  end
end

如果这个脚本搜索到了一个子目录，那么它会用这个子目录调用find_directories。这样脚本就可以搜索任意层数，不会遗漏任何子目录。

总结

递归是处理任意多层事情的算法的绝佳选择。

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