《编程机制探析》第十五章 递归

《编程机制探析》第十五章 递归

前面章节讲述的基本上都是命令式语言（Imperative Language）的编程模型。关于命令式编程（Imperative Proramming）的重要概念和模型，我们基本都涉及到了。后面的章节将开始讲述另一种编程模型——函数式编程（Functional Programming）的内容。
在讲述函数式编程（Functional Programming）之前，我们需要做一些知识上的储备——递归（Recursion）。
其实，我们在前面的章节中，已经遇到过递归了。在前面的“Iterator Pattern”章节中，树形结构的遍历算法代码就是递归形式的。递归是一种过程自调用的一种代码形式，看起来没什么大不了的。但是，递归对于函数式编程来说，却是极为重要的一门必须掌握的代码形式。
为什么这么说呢？因为，在函数式编程中，递归是实现代码多次重复运行的唯一形式。函数式编程只支持递归，不支持循环。
在命令式编程中，代码多次重复运行有两种形式。一种是循环形式，比如，for、while等语法形式；一种是递归形式。
在命令式语言的实际使用中，循环比递归用得多得多。原因很简单。过程内部可以直接定义循环体，两者在同一个过程的作用域内，循环体代码可以直接使用本过程作用域内定义的局部变量，用起来很方便。但是，递归涉及到的过程调用，相当于进入到另一个过程的作用域，两个过程的局部变量并不能通用，两个过程只能依靠参数和返回值来进行数据交流，写起来麻烦许多。
在某些情况下，比如树形结构的便利算法中，递归会很方便，比循环还要方便。但是，大部分情况下，循环要比递归方便。
既然循环更加方便，为什么函数式编程不支持循环呢？函数式编程不是不想支持循环，而是支持不了。
为什么函数式编程支持不了循环呢？因为，在函数式编程语言中，变量表现得如同常量一般，非常专一，一生只能被赋值一次，之后就不能再改变了。从一而终，一生不二嫁。这就是函数式变量的忠贞品质的真实写照。
而循环是什么？循环本质上是基于Iterator Pattern的，需要一个Iterator来提供当前元素，并保存集合遍历的当前状态。所以，循环形式有个名字叫做Iterative（有些资料翻译成迭代）。
最简单的情况，循环也至少需要一个计数器，来保存当前循环的步数。无论是Iterator，还是计数器，都是需要与时俱进、随时改变的。终生不变的函数式变量根本就无法满足成为Iterator或者计数器的要求。所以，函数式编程从根子上就无法支持循环，只能支持递归。
读者可能会担心，函数式编程不支持循环，功能上是否不够全面？
这点不用担心。循环和递归在计算模型上的实现能力完全等价。循环能够实现的功能，递归也一定能够实现。反之亦然，递归能够实现的功能，循环也一定能够实现。而且，循环和递归这两种形式是完全可以相互转换的。循环形式，一定能够转换成递归形式。而递归形式也一定能够转换成循环形式。
命令式语言的程序员习惯了循环形式，函数式语言的程序员习惯了递归形式。命令式语言的程序员若想学习和使用函数式编程，必须掌握循环到递归的转换方法。函数式语言的程序员若想学习和使用命令式编程，必须掌握递归到循环的转换方法。若是两种编程模型都想深入掌握的程序员，则必须掌握循环和递归的相互转换，既要掌握循环到递归的转换，也要掌握递归到循环的掌握。
本章的中心内容就是讲解循环和递归这两种形式的相互转换。本章希望帮助读者达到如下的目标：更深入地理解循环和递归这两种形式的本质；加深对函数调用和运行栈的理解；更有效地使用参数和返回值在进程调用间传递数据；更有效地理解和使用数据结构。
首先，我们来看几组递归形式的重要概念。
关于递归的第一组重要概念是：直接递归和间接递归。
直接递归是这样一种递归形式——函数调用自身，比如：
f(…) {
  …
  f(…)
  …
}
间接递归是这样一种递归形式——函数f并不直接地调用自身，而是调用了其他的函数g，而函数g又调用了函数f，这就形成了一个间接递归。比如：
f(…) {
  …
  g(…)
  …
}
g(…) {
  …
  f(…)
  …
}
这种间接递归可能不止一次“间接”，可能经过多次“间接”。比如，f调用g，g调用h，h调用m，m调用f。不管中间有多少次“间接”，只要最终形成了对自身的调用，那就是递归形式。
有时候，我们通过代码形式看出间接递归形式。有时候，递归结构是在运行时建立的，我们无法从形式上直接看出来。比如，下面的示意代码：
interface Calculator{
  int calculate(int n);
}

class FactorialCalculator implements Calculator{
  Calculator delegate;
 
  int calculate(int n){
if(n <= 1)
  return 1;

return n * delegate.caculate(n - 1);
  }
}
FactorialCalculator factorial = new FactorialCalculator();
factorial.delegate = factorial; // delegate指向自己，形成了递归调用的事实
factorial.calculate(10);
所以，我们要注意，有时候，不存在递归形式的代码也有可能形成递归调用的事实。
间接递归和直接递归只有形式上的不同，在概念上没有什么不同。我们平时遇到最多的递归形式是直接递归。本章讨论的递归形式基本上都是直接递归。间接递归只是形式上有些绕而已，本质上和直接递归没什么区别。
关于递归的第二组重要概念是：线性递归和树形递归。
线性递归是指递归函数的代码中只存在一次对本身的调用，比如上面的示意代码，都是线性递归。
线性递归在运行时，运行栈会一直向上增长，增长到头之后，就会一直向下减少，直到最后递归结束。也就是说，在线性递归的整个执行过程中，运行栈只发生一次伸缩。线性递归无论是形式上，还是执行上，都比较简单。线性递归转换成循环形式，相对比较简单。
一般来说，线性递归通常发生在线性数据的遍历算法中。
树形递归是指递归函数的代码中存在两次或两次以上的对本身的调用，比如：
f (…) {
  …
  f(…)
  …
  f(…)
  …
}
另外，如果对自身的调用发生在循环体中，也是一种树形递归，比如：
f (…) {
  …
  for (…)
f(…)
  …
}
这种递归在执行的时候，在一个过程体内会产生多次递归，从而产生多次运行栈的伸缩，看起来像一棵有多个分支的树，所以叫做树形递归。在树形递归的执行过程中，运行栈时而增长，时而缩减，伸缩不定，有可能发生多次伸缩。因此，无论是形式上，还是执行上，树形递归都要比线性递归复杂得多。树形递归转换成循环形式，相对比较复杂。
一般来说，线性递归通常发生在树形数据的遍历算法中。
需要注意的是，有些递归形式看起来像树形递归，实际上却是线性递归。比如这样的代码：
f (…) {
  …
  if(…)
f(…)
  else
  f(…)
  …
}
上述代码中，看起来像是两次递归调用，但由于这两次递归调用是存在于不同的条件分支中，实际上，在执行的时候，只可能有一次递归调用。因此，这种递归是线性递归。
所以，我们在分辨递归的时候，不能只关注形式，还要关注事实。
关于递归的第三组重要概念是：尾递归和非尾递归。
在线性递归中，有一种特殊的情况。递归调用是函数体中执行的最后一条语句。比如：
f(…){
…
f(…)
}
注意，一定要保证，递归调用是函数体中最后一条执行的语句，才能满足尾递归的条件。
f(…){
…
return 1 + f(…)
}
这样的写法中，f(…)虽然看起来是函数体中的最末一句。但是，在执行过程中，却不是最后一步。最后一步是“+”这个操作。
有时候，代码看起来不是尾递归，实际上却是尾递归。比如：
f (…){
  if(… ){
…
return f (…)
  }

  if(… )
return 1
}
上述代码中，递归调用并不是函数体中的最后一条语句，但在执行上却是最后一句。所以，这也是尾递归。还有：
f (…){
  if(… )
return f (…)
  else if (…)
    return f(…)
  else
return 1;
}
也是尾递归。
至于什么是“非尾递归”，很简单，不是尾递归的递归，都是“非尾递归”。
线性递归可能是“尾递归”，也可能是“非尾递归”。
对于“非尾递归”的线性递归，我们用一个固定长度的数据结构来存放中间结果，就可以把“非尾递归”的线性递归都可以转换成“尾递归”形式。
树形递归一定是“非尾递归”，我们用一个复杂结构（模拟运行栈的伸缩不定的数据结构）来存放中间结果，就可以把树形递归转换成尾递归。
读者可能会问，我们为什么非要把“非尾递归”的线性递归转换成“尾递归”形式？
有两个理由，第一个理由是为了循环和递归的转化，第二个理由是为了空间和时间上的优化。
我们来看第一个理由——循环和递归的转化。
尾递归是一种最接近循环的递归形式。尾递归已经是递归向循环转换的最后一步，只要变换一下形式，尾递归就变成了循环。
递归向循环转换的常用手段就是，先把递归变成尾递归，然后再把尾递归变成循环。同理，循环转换成递归的最直接方法就是转换成尾递归。
我们这里就能够看到理论模型上的一致：正如所有的递归都能够转换成循环，所有的递归也都可以转换为尾递归。
再来看第二个理由——空间和时间上的优化。
这是一种“可能的优化”——主要是空间上的，也有一点时间上的。
由于尾递归在本质上已经等于循环，有些编译器（或者解释器）会对尾递归代码进行优化，在发生递归调用的时候，不需要保存所有的中间结果，因而并不进行真正的压栈操作，而是如同处理循环一样直接运算。这种优化不会引起运行栈的一层层的增长，从而节省了空间。在递归层次非常深的情况下，这种优化尤其有意义。
对于函数式程序员来说，尾递归更是一种必须掌握的技能。因为，非尾递归的运行栈是随着递归深度增长而不断膨胀的。如果递归层次过深，就会引起运行栈溢出（即空间不够了）的错误。
有些服务程序（或者图形界面程序）需要长期运行在计算机中，这实际上是通过无限次重复运行（计算机术语叫做死循环）来实现的。死循环的递归形式就是无限次递归。如果是非尾递归，必然会引起运行栈溢出的错误。因此，在函数式语言中，需要长期运行的死循环结构的程序（如服务程序或者图形界面程序）必须写成尾递归的形式不可。
至于时间方面，自然压栈和出栈的时间上的节省。有些特殊情况下，尾递归甚至可以引起算法上的优化。比如，有时候，树形递归会引起重复递归计算，这时候，尾递归就可以有效地消除重复计算步骤，从而优化算法，节省时间。当然，这只是特殊情况，大多数情况下，树形递归是无法优化的。比如，树形结构的遍历，你就得老老实实遍历所有结点，才能完成算法，没有捷径可走。
综上所述，尾递归的重要性是怎么强调也不为过的。
现在，我们从最简单的例子讲起——阶乘（factorial）。关于阶乘的数学定义为
n!=1×2×3×……×n
用数学归纳法表示为
n!=n×(n-1)!
根据第一种数学定义，阶乘算法很容易用循环形式写出。
int factorial(int n){
  int result = 1;
  for(int i = 1; i <= n; i++){
    result = result * i;
  }
  return result;
}
根据第二种数学定义（归纳法表示），阶乘算法很容易用递归形式写出。
f(1) = 1
f(n) = n * f(n-1)  // n > 1

int f(n){
  if(n = 1)
return 1;
  else
    return n * (n-1);
}
注意，为了简化问题起见，以上的代码忽略了n < 1的情况。真正运行的代码一定要把这种情况考虑进去。
我们看到，同一个阶乘问题，我们可以写成循环和递归两种形式。
以上的递归算法中，最后一步操作是“*”（乘法），而不是递归调用，所以，并不是尾递归算法，只是一种最直观的递归算法。递归调用自身之后，还要进行一个乘法计算。这意味着栈内的所有中间结果都是需要保留的。
如果要写成尾递归的形式，关键是要让乘法计算发生在递归调用之前，而且要把乘法结果保存在下一次递归调用能够访问的变量中。
命令式程序员对循环形式很熟悉，很容就想到用循环体外的局部变量来存放中间结果。比如，上面的factorial循环算法中定义的result变量。
函数式程序员脑海中没有循环的概念，只有递归的概念。对于递归，他们早已得心应手，一看到中间结果，首先想到的就是用参数和返回值来传递中间结果。因为，在函数式语言中，变量只允许赋值一次，不能用来存放随时变化的中间结果，只能利用参数来传递中间结果。
我们应该如何把上述的factorial递归算法转换成尾递归的形式呢？对于我们命令式程序员来说，最简单的做法就是从循环算法开始转换。具体做法就是把循环体中用到的所有变量都变成递归调用的参数。
前面已经有了factorial的循环算法。我们来考察其中的循环体在每一个循环步骤中用到的所有变量。
首先，i 和 result 这两个变量，是一定要有的。i 表示的是当前步骤，result存放的是中间结果。
其次，n 这个变量也是要有的。因为，在每一个循环步骤中，都需要判断 i <= n，从而判断是否结束。在递归算法中，我们需要做同样的判断来决定递归是否结束。
综上所述，递归函数的参数就确定了，就是以上的i、result、n这三个变量。至于递归函数的返回值，自然是当前计算的结果。
这样，循环算法中的循环体就可以修改成这样的递归代码。
int factorial(int i, int result, int n){
  int result = result * i;

  if(i >= n)
return result; // 结束递归

  return factorial(i + 1, result, n); // 把本次的计算结果向下传，继续递归
}
这种递归算法几乎和循环算法一模一样。递归体内与循环体的代码逻辑顺序是完全一致的：先做乘法计算，然后根据i与n的比较结果，决定是继续递归，还是结束递归。
所以，对于我们命令式程序员来说，若想把非尾递归转换成尾递归，最方便的方法就是先写出循环算法，然后根据循环体内的执行逻辑顺序，构造出一个尾递归函数。
以上的factorial尾递归算法多了两个没有必要的参数——i和result。我们可以用一个包装函数来消除这两个多余参数。
int neat_factorial(n) {
  return factorial(1, 1, n);
}
函数式程序员的考虑则是直接从结果来考虑。既然尾递归是最后一步操作。那么，所有的计算过程必然要在尾递归发生之前完成。然后根据当前运行步骤，判断结束递归，还是继续递归。这种思路与命令式程序员的思路殊途同归，但造成的结果还是有些细微的不同。
命令式程序员的思考起点是循环算法，是从1乘到n，从小到大的升序乘法。而函数式程序员的思考起点是递归算法f(n) = n * f(n-1)，是从n乘到1，从大到小的降序乘法。在这种降序的乘法中，我们可以省掉i这个用来代表当前步骤的参数。尾递归就可以写成这样：
int factorial(int result, int n){
  int result = result * n;
  if(n <= 2)
return result;
  return factorial(result, n - 1);
}
其包装函数为：
int neat_factorial(n) {
  return factorial(1, n);
}
这个尾递归转换成循环就是这样：
int factorial(int n){
  int result = 1;
  while(n > 1){
result = result * n;
n = n – 1;
  }
return result;
}
如果命令式程序员以这个循环算法为起点，得到的尾递归算法就是省掉了i参数的这个版本。
上述例子是线性递归，是最简单的递归形式。线性递归主要是针对线性结构的。对于线性结构来讲，算法的时间复杂度都是线性的。不管怎么折腾，管它是循环还是递归，抑或尾递归，时间复杂度都是一样的。
下一章，我们将讲解更复杂的、也是更主要的递归结构——树形递归。我们将看到，相对于线性结构而言，树形递归无论在空间复杂度上，还是在时间复杂度上，都要复杂许多。因此，树形递归通常拥有更大的算法优化余地。