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

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

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

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

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

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

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

将这种运算过程转换为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)。它的执行过程如下图所示:

我们可以比较前面线性递归过程的执行结果,很显然,线性迭代过程的执行步骤要远远少于前者。本质上,虽然尾递归名为“递归”,其实执行的是一个迭代过程。在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。

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

2017-02-17 20:0763FPScala