艾舍尔的《画手》与尾递归

画手

这是一幅奇妙的图，如你所见，画中的两只手各自画着对方，当我们明晓这样一种怪异的循环时，一瞬间，仿佛这张静止的画突然流动起来，而且是一种永恒的运动，作画的两只手似乎永远无法停止。正如《哥德尔艾舍尔巴赫》一书的作者侯世达在评价艾舍尔的这幅《画手》时提到的：

《画手》给我们提供了一个更紧凑的圈，这幅画中的每一只手都在画另一只手：这是个只包含两个阶段的怪圈。

侯世达在巴赫的音乐、艾舍尔的绘画以及哥德尔不完全定理中发现了“怪圈”这个概念。

所谓“怪圈”现象，就是当我们向上（或向下）穿过某种层次系统中的（这里，系统是音乐的调子）一些层次时，会意外地发现我们正好回到了我们开始的地方。有时我用“缠结的层次结构”这个词来形容出现怪圈的系统。

我在阅读《哥德尔艾舍尔巴赫》这本书时，改不了作为程序员的积习，尤其当我看到这幅令人震撼的《画手》时，我即刻从“怪圈”想到了“递归（Recursion）”。因为“递归”正是这样自身调用自身的编程技巧。当然，一段正确的递归程序，必须要有一个必定能够到达或满足的终止条件，否则就会像《画手》那样永恒地循环下去。程序术语称之为“死循环”。

递归可以让代码变得极为简洁，这种逐步递减而又自我调用的方式确有一种神秘意味，然而，它却并非是一种高效的算法实现。仔细琢磨递归的运算轨迹，会发现它最终形成了“先逐步展开而后收缩的形状”，如下图所示：

计算6!的线性递归过程，图片来自SICP

将这种运算过程转换为scala代码，则如下所示：

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

《Structure and Interpretation of Computer Programs，计算机程序的构造和解释》（简称SICP）对递归进行了深刻的阐释：

这一过程构造了一条推迟执行的操作链条，收缩阶段则表现为这些操作的实际执行。这种过程被称之为“递归过程（recursive process）”。要执行这一过程，需要解释器记录后面要执行的操作。在计算阶乘n!时，推迟执行的乘法链条的长度也就是为保存其轨迹需要保存的信息量，这个长度随着n值而线性增长，故而称为“线性递归过程（linear recursive process）”。

正因为此，递归固然让代码变得简洁，但由于它要保存推迟执行的操作，链条越长，需要保存的信息越多，因而执行的效率取决于这条“链条”的长度。

让我们再回过头来看艾舍尔的《画手》。在这个左手画右手，右手画左手无限纠缠的怪圈之外，实际上“隐藏着一直未画出但正在画的手，它属于艾舍尔，左手和右手二者的创作者。”

“艾舍尔处于这两只手所在的空间之外”，因此能够做到旁观者清。侯世达将其视为两个不同的层次，如下图所示：

艾舍尔《画手》的抽象示意图，图片来自侯世达著作《哥德尔艾舍尔巴赫》

以阶乘运算为例。阶乘本身其实不应该陷入到自我调用的递归圈中，正如绘画的艾舍尔应该置身怪圈之外。递归仅应该出现在递进的运算中，每次递进的结果则作为参数传入到递归的函数中。正如SICP对阶乘运算的分析。线性递归的算法体现的是阶乘运算的朴素数学知识，即：对于一个正整数n，n!就等于n乘以(n-1)!。

除此之外，SICP给出了另外一种观察的视角：

我们可以将计算阶乘n!的规则描述为：先乘1和2，而后将得到的结果乘以3，而后再乘以4，这样下去直到达到n。更形式地说，我们要维持着一个变动中的乘积product，以及一个从1到n的计数器counter。

我们需要将计数器counter与变动的乘积product抽离出来，放到如侯世达所说的“可见的层次结构”中，即单独定义一个函数factIter：

def factorial(n: Int): Long = {
  def factIter(product: Long, counter: Int, maxCount:Int): Long =
    if (counter > maxCount) product
    else factIter(product * counter, counter+1, maxCount)
  factIter(1, 1, n)
}

在factorial函数内部定义的函数factIter实现了递归，它有一个特征是方法的尾部是且只能是对函数自身的调用。

product变量就是前面我所谓的“每次递进的结果”，也就是SICP中提到的“变动中的乘积”。准确来讲，应该将product看作是一个accumulator。它每次存储的都是每一步计算的结果，然后通过其汇集，最后收获最终的运算结果。至于counter与maxCount变量的引入，不过是为了完成递进的运算，以及给出终止运算的满足条件而已。

SICP认为：

（这种运算过程）并没有任何增长或者收缩。对于任何一个n，在计算过程中的每一步，在我们需要保存的轨迹里，所有的东西就是变量product、counter和maxCount的当前值。我们称这种过程为一个迭代过程（iterative process）……在计算n!时，所需的计算步骤随着n线性增长，因而被称为线性迭代过程（linear iterative process）。

由于其特性是内部的函数总是在函数尾部被递归调用，故而这种调用方式又被称之为尾递归（tail recursive）。它的执行过程如下图所示：

计算6!的线性迭代过程，图片来自SICP

我们可以比较前面线性递归过程的执行结果，很显然，线性迭代过程的执行步骤要远远少于前者。本质上，虽然尾递归名为“递归”，其实执行的是一个迭代过程。在Scala或者其他很多语言中，尾递归就是一种编译技巧。例如当Scala发现某个递归调用其实是一个尾递归时，会自动将该递归编译为循环迭代，从而避免了每次进行栈的操作（因为递归需要记录延迟运算）。Scala还提供了@tailrec标记来标识尾递归。若你编写的递归函数不是尾递归，只要标记了@tailrec，编译时会提示错误。

要将一个递归过程编写为迭代过程，而又要避免显示地循环调用方式，关键之处就在于我们要转换视角（跳出互相绘制的两只手）。个人认为，“四两拨千斤”的着眼点就是寻找accumulator。

我在项目中希望对一个类似树结构的样例类做一次“拍平”的操作。定义如下：

case class BindingElement(itemType: BindingItemType, fieldId: ID, children: Option[List[BindingElement]])

BindingElement的内部“可能”嵌套了子的BindingElement列表。而子列表中的BindingElement也可能继续嵌套。如此的嵌套自然就形成了一棵树，且非最简单的二叉树。

需求要求将根节点BindingElement嵌套的所有子节点（包括间接嵌套）全部拍平，最后形成一个没有任何子节点的BindingElement列表。

我在实现时，直觉告诉我这个“拍平”的动作其实就是对一棵树的遍历，完全可以用尾递归来完成。可是写了许久，都未能将这个尾递归函数实现。问题的症结就是我没有去寻找关键的accumulator。实质上，针对这个场景，我们要返回的结果是List[BindingElement]，在迭代过程中，就是每次叠加的值。初始值则为Nil。这里没有阶乘运算中的counter与maxCount，而是一个作为children的List[BindingElement]。因为参与递归的结构是列表中每个BindingElement中的children，对于List而言，我们可以判断其值是否为Nil来作为终止条件。

找到了accumulator，尾递归的迭代算法自然就水到渠成了。代码如下所示：

case class BindingElement(itemType: BindingItemType, fieldId: ID, children: Option[List[BindingElement]]) { 
  def flatten:List[BindingElement] = { 
    def cloneToLeaf(item: BindingElement) = BindingElement(item.itemType, item.fieldId, None) 

    @tailrec 
    def traverse(items: List[BindingElement], acc: List[BindingElement]): List[BindingElement] = 
      items match { 
        case Nil => acc 
        case head :: tail => traverse(head.children.getOrElse(Nil) ::: tail, acc :+ cloneToLeaf(head)) 
      }

    traverse(children.getOrElse(Nil), List[BindingElement](cloneToLeaf(this))) 
  } 
}

注意，这里的acc（即accumulator）在Scala中其实是一个不变的变量；所以通过运算符:+添加元素项后得到的是另外一个List。然而，作为accumulator，其实它是以参数形式传递给下一个迭代，故而下一次迭代中的acc已经变成了累加了元素后的结果，这是traverse函数之所以能够奏效的原因。

因为尾递归函数tranverse遍历的是List[BindingElement]，这会导致返回的结果会缺失根元素自身，所以在初始化acc时，将根元素（即this）赋值给了acc。

递归充满了艺术的神秘美感，而尾递归则在艺术美与工程高效之间取得了平衡。《画手》的两个层次（可见的和不可见的）给了我们一个启发，就是在观察事物时，需要尝试不同的视角，要学会跳出具体的实现细节，找到职责上的抽象分解。对于程序员而言，我们还可以尝试跳出计算机科学的范畴，从绘画、数学、建筑或者音乐中寻找到灵感，利用跨界思想来体悟软件设计与编程。