尾递归的启示

——读《计算机程序的构造和解释》第一章第二小节所想

尾递归是指在过程调用中，递归调用过程本身的操作始终是过程的最后一步。举例来讲，计算阶乘的方法，根据定义，直接翻译成递归形式为

def factorial(n):
  if n == 1:
    return 1
  else:
    return n * factorial(n-1)

这个递归中，最后一步操作是乘法，而非调用过程本身，因而不是尾递归。转换成尾递归的形式如下

def factorial(n):
  return factorial_iter(1, 1, n)

def factorial_iter(product, counter, max_count):
  if counter > max_count:
    return product
  else:
    return factorial_iter(product*counter, counter+1, max_count)

使用尾递归的好处，可以从两方面来看，一则是同非尾递归过程比较的优势，另一则是同程序设计语言中专门的循环结构（也可以称作迭代结构）比较的优势。

不论是同非尾递归过程比较还是专门的循环结构比较，都先需要明确的是过程调用意味着什么，过程到底是什么。

初学程序设计的人会说，过程不就是一个函数么，接收一些输入，返回一些输出，有什么可以深究的呢。过程的概念初听，理解起来非常容易，但能清晰地想清楚如何利用好过程以及明白过程带来的意义并非显而易见。

了解清楚过程，要从两个方面来看待，一方面是过程在如何影响我们设计和组织程序，另一方面是过程在如何指挥计算机执行任务。

好的过程设计，会明确过程的输入和输出，过程的命名也明确意味着要执行的任务，整个过程如同黑盒子一般，除了依赖输入和输出之外，不会依赖其它的任何东西。物理世界中，人们生产的无数优秀的生活用品、科技产品都具有这个特性。比如水龙头，接水管的口径是明确的，操作水龙头闭合和打开的阀门是明确的，输出口的口径也是明确的，进而水流的速度也是可调控的。再比如白炽灯，螺纹接口的尺寸和样式是明确的，电灯消耗的电功率是明确的，输入的电压范围是明确的，电灯的材料是明确的，进而发光的亮度也是可调控的。物理世界中的物品，人们很容易注意到他们的依赖，也就是使用条件或者说输入和输出。当场景切换到计算机软件，逻辑的世界中，模块就如同物品，过程就是模块的基本构件。有人会觉得模块听起来像是静态的，过程听起来像是动态的，怎么能说是一回事。仔细想想，其实现实中的物品又有什么是完全静态的呢，不论水龙头还是白炽灯。从自然语言上来看，所有的动词又何尝不是一个名词呢，我们给一种动作起了个名字就是动词所表达的含义。逻辑的世界中，过程封装了一系列的指令用于去完成某个任务，而过程本身对设计者而言意味着一条新的计算机指令。软件本身就是一个复杂的过程，优秀的计算机软件都有着这样的设计。

于计算机而言，一个过程有外部的环境，有内部的环境。设计良好的过程对外部的依赖应该仅局限于输入的参数提供的内容，暴露给外部环境的应该仅局限于输出的返回值。内部的环境不应该修改外部环境的任何内容，返回结果也应该始终稳定前后一致。过程的嵌套调用给环境的维护带来了一些开销。写过汇编语言的人知道每个调用指令执行时都要先将当前的寄存器状态压栈，然后才会加载新过程的指令。每个线程都会有各自的栈用来保存这些状态。高级语言中，也有类似的情形，当函数调用开始之后，实际参数替换了形式参数后，实际参数也都需要保存，以免出现调用返回之后找不到符号的问题。调用层次较多的非尾递归程序因为这样的原因，就需要更多的空间去保存调用前的参数状态，从而造成空间的浪费。然而尾递归却不用有这个忧虑，编译器通常会做优化，如果发现是尾递归，那么实际参数不会再被使用，调用之前的状态也就不必保存。

非尾递归除了有明显的空间浪费外，往往还会有明显的重复计算，由于参数的保存，仅限于参数，并不会根据具体的问题，保存一些已经计算过的中间状态。这些重复计算在树形结构的调用中往往是巨大的。尾递归由于没有系统栈帮着保存状态，就要求程序设计者设计合理的参数来保存计算过程中的必要的中间状态，从而既减少了重复计算，又减少了空间浪费。

拿前面阶乘的例子来看，product就是用来保存中间状态的参数，counter是用来控制迭代次数的参数。尾递归实现中通过增加这两个参数，将空间开销由O(n)减到了O(1)。阶乘的例子由于是线性递归，所以不存在重复计算，但即便如此，非尾递归的实现中也需要先展开再规约，而尾递归的实现中只需要一遍就能得到结果，计算量也会减少一半。

很多的问题的递归解法，呈现出树形递归的特点，即原问题的解决依赖于多个相同子问题的解决，比如换零钱的问题。

假设只有50美分、25美分、10美分、5美分和1美分的面值，如果将给定数额的钱用前面提到的五种面额兑换，那么有多少种换法？

这个问题跟求组合数的问题非常类似，可以将原问题分解为两个子问题。第一，完全不用50美分兑换，用剩下的四种面值兑换给定额度的钱；第二，用一个50美分兑换，对于除去50美分剩下的钱再用五种面值去兑换。这两个子问题彼此互斥，所以求和就是原问题的解。用程序语言描述即为

def rec_count_change(amount):   return rcc(amount, 5) def rcc(amount, kinds_of_coins):   if amount is 0:     return 1   elif amount < 0 or kinds_of_coins is 0:     return 0   else:     return rcc(amount, kinds_of_coins-1) 
           + rcc(amount-first_denomination(kinds_of_coins),
                 kinds_of_coins)

def first_denomination(kinds_of_coins):
  coins = [0, 1, 5, 10, 25, 50]
  return coins[kinds_of_coins]

这个解法显然不是尾递归，最后一步操作是加法，不过非尾递归的解法往往非常容易辅助在脑海中产生求解问题的分解结构。分解的结构是棵二叉树，树的叶子节点要么是0，要么是1，因而叶子的数目与问题的结果是同量级的，这其中的重复计算量是巨大的。当amount是100时，问题的结果是292；当amount是1000时，问题的结果是801,451。虽然amount只增长了10倍，但结果却增长了2700多倍，这是超线性的增长。此外，这棵树不太平衡，如果记rcc(amount, kinds_of_coins-1)为左子树，另外一个为右子树，那么由于kinds_of_coins很快就减到了0，所以左边的深度较浅，最左边的深度只有kinds_of_coins+1；右边由于50美分减得很快，深度也较浅，最右边的深度为int(amount/50)+1，最深的部分在中间为amount+kinds_of_coins+1，所以整棵树像是一串葡萄一样。最大的深度也意味空间开销与amount+kinds_of_coins是同量级的。

将这个问题改造成尾递归的形式，需要两点技巧，第一，尾递归一般意味着自底向上地先求解最终问题依赖的子问题的结果，因而需要在参数中增加适当的变量，开辟适当的空间，用于存储中间子问题结果，空间的大小越小，不仅省空间，往往同时也会提升运行效率；第二，当问题中有两个以上的输入时，就需要找对迭代的方法和维度，这点往往对节省空间起着至关重要的作用。

如果用表格记录所有可能子问题的结果，那么表格一定只有(amount+1)*kinds_of_coins的大小，共有kinds_of_coins行，amount+1列。在求解表格中任何一个格子中的值时，都只依赖于前一行同列（kinds_of_coins-1, amount）与同行前面某列（kinds_of_coins, amount-first_denomination(kinds_of_coins)）的值，如果我们逐行地填充表格，就不必要保存着整张表，而只需要一行的存储空间。这样的空间开销不会比非尾递归大，时间上要远好。想清楚了第一点技巧，还要想清第二点，也就是说，起始时候，amount从0开始，kinds_of_coins从1开始计算，到底是先固定amount为0不变，将所有的kinds_of_coins都算出来呢，还是相反将kinds_of_coins固定为1，而去计算出对应所有amount的值。其实在选择存储空间大小时候，就已经潜在回答了这个问题，我们选择了一行，即为后者。明白了改造尾递归的两个方面，改起算法来也不会非常困难。尾递归的解法为

def tail_rec_count_change(amount):
  return trcc(amount, 5, 0, 1, [0]*(amount+1))

def trcc(amount, kinds_of_coins, ca, ck, arr):
  if ck > kinds_of_coins:
    return arr[amount]
  elif ca > amount:
    return trcc(amount, kinds_of_coins, 0, ck+1, arr)
  else:
    if ca == 0:
      arr[ca] = 1
    else:
      remain = ca - first_denomination(ck)
      if remain >= 0:
        arr[ca] = arr[ca] + arr[remain]
    return trcc(amount, kinds_of_coins, ca+1, ck, arr)

尾递归相比于专门的循环结构，既保持了原始递归分解的形状，又拥有了动态规划自底向上的实质。这两个特点是极其优秀的，人们思考问题时最自然的方式是自顶向下的分解，几乎所有的问题都如此，否则大型系统的构造无从谈起。从原始递归转换为尾递归时，设计者可以专注于寻找适当的存储空间，放在参数中即可，而专门的循环结构往往会干扰设计者的思路。循环结构中循环控制变量，会让人不停地去重复在大脑中运行循环，而不是去思考寻找适当的存储空间和解决小的子问题。我非常同意《计算机程序的构造和解释》一书中作者对尾递归存在意义的评价：“有了一个尾递归的实现，我们就可以利用常规的过程调用机制表述迭代，这也会使各种复杂的专用迭代结构变成不过是一些语法糖衣了”。面对复杂的算法，优先写出递归解法，再改造成尾递归形式，然后再用专用的循环结构去改造不失为一种好的策略。实际上，循环结构是机器友好的，并不是人类友好的，循环天然拥有着一种自底向上的特质，只适合于做，不适合于想。从尾递归改造成循环结构难度要小于从原始递归转变为尾递归。从原始递归转变为尾递归，需要思路上的转变，而从尾递归转变为循环结构，如同找了一些同义词，从新表达一个段落而已。

然而，值得注意的是并不是所有的语言都适合写成尾递归的形式，很多解释型的语言并没有对尾递归做优化，比如上面所用的Python语言。编译型的语言多会对尾递归做优化，比如C、Java。我尝试在Python上运行tail_rec_count_change(1000)，结果抛出了RuntimeError: maximum recursion depth exceeded的异常，而在Java的虚拟机上运行，则会给出正常的结果。由此，尾递归适合用于辅助我们思考较为复杂的算法问题，最终实现时要改造为循环结构的迭代形式。

后记

除了换零钱的例子外，求解组合数、求幂的O(log n)算法、求数组的子数组之和的最大值也都是良好的练习，相应的解法可以参考这里。

相关阅读

• 求数组的子数组之和的最大值?⭐️⭐️⭐️⭐️