粗看递归

   第一次写blog，答应朋友Leon，写一篇粗略地介绍“递归（recursion）”的文章。
   递归，一种古老但依旧实用的东东，很多算法用递归方法表示，用递归写的程序也很容易让人理解。
   递归的优美在于使得程序更简洁，同时也更自然。尤其是在处理层次性数据的时候，十分强大。当然，递归的缺点也十分明显--性能问题。在性能这个问题点上， 有一种手段能适当改善递归的性能--尾递归（尾递归的概念将在下文解释）。关于优缺点就此打住，还是很容易理解，我就不婆婆妈妈的罗嗦了，我直接切入正 题。
   
什么是递归？
    在这里我们区分一下几个概念“递归过程”和“递归计算过程”以及相对应的“迭代计算过程”。
“递归过程”通常是指某个过程（方法）的定义直接或间接地引用了该过程（方法）本身。在本文中如非特别说明，“递归”这个词泛指一个或某种“递归过程”，而在描述递归型计算过程的时候都会用“递归计算过程”。
下面是一个array求和的递归方法

ruby 代码

def sum(arr)
  if arr.empty?
    0
  else
    arr.shift + sum(arr)
  end
end

这是一个递归，同时也是递归计算过程的递归。来看看sum函数在1..5上的求值过程

ruby 代码

[1,2,3,4,5]
1 + sum([2,3,4,5])
1 + (2 + sum([3,4,5]))
1 + (2 + (3 + sum([4,5])))
1 + (2 + (3 + (4 + sum([5]))))
1 + (2 + (3 + (4 + (5 + sum[]))))
1 + (2 + (3 + (4 + (5 + 0))))
1 + (2 + (3 + (4 + 5)))
1 + (2 + (3 + 9))
1 + (2 + 12)
1+ 14
15

通过这个求值过程，很容易看出sum函数有明显的展开和收缩（收敛）过程。类似这样先展开/后收缩（收敛）的推迟求值的过程就是“递归计算过程”。
    知道了什么是“递归计算过程”后，再来瞧瞧“迭代计算过程”。代码在这里是最佳的说明，我们稍微改变一下sum函数用迭代计算过程来求值。

ruby 代码

def sum_iter(arr, resu = 0)
  if arr.empty?
    resu
  else
    resu += arr.shift
    sum_iter(arr, resu)
  end
end

ps:sum_iter的写法有时候也会被称为尾递归写法。怎么又是尾递归？稍安毋躁，我发誓接下来我一定会说到“尾递归”的！

它在1..5上的求值过程如下

ruby 代码

[1,2,3,4,5]
[  2,3,4,5] + 1
[    3,4,5] + 3
[      4,5] + 6
[        5] + 10
[         ] + 15
15

在这个计算过程中，平没有明显的展开和收缩（收敛）过程，在整个运行轨迹中我们只需保存变量resu。这种所有程序状态可以用固定个数的状态变量，以及一套固定的状态变量的修改规则就是“迭代计算过程”。相比递归计算过程，迭代计算过程有一个优点就是可以保存程序运行中的某个状态，然后下次运行的时候可以直接传递这个中间状态给该过程以恢复上次运算。你可以传递[4,5]和6给sum_iter，它仍然能计算出15，而你传递[4，5]给sum，结果是9。

线性递归和树形递归
    也许当你看到sum和sum_iter的时候，你更喜欢用for，foreach和while这样的循环来处理。实际上有一部分递归可以很容易地转换为循环，然而另一部递归却并不那么容易的进行转换。是否能容易转换为循环，取决于它是否是迭代/递归计算过程和线 性/树形递归。毫无疑问，拥有迭代计算过程的递归可以迅速转换为循环。迭代计算过程的递归和循环处理基本上是等价的，因此某个递归能不能转换为 迭代计算过程的递归也就决定了它能不能转换为循环处理。至于为什么要把递归转换为循环处理，可以看看【然而它工作得不过好】。
    现在我们可以回到这一节的主题线性/树形递归。性/树形递归这个其实很好理解，就像sum和sum_iter这样的程序的计算步骤是随参数arr而线性增长的，这种过程就是线性递归。线性递归还可以细分为线性递归计算过程和线性迭代计算过程的递归，分别对应sum和sum_iter。关于树形递归我就不多说了，可以很容易地联想到Tree这种结构。树形递归的也是先展开后收缩的，只不过它的展开后的求值过程是一棵树。这个不难联想到实际情况，例如自己写程序求某个目录下面的所有文件数或查找某个文件。但是这里有一点必须要注意。树形递归的效率比线性递归低得多。
例如，求fibonacci数

ruby 代码

def fib(n)
  if n == 0 : 1
  elsif n == 1 : 1
  else
    fib(n-2) + fib(n-1)
  end
end

def fib_iter(n, a = 1, b = 0)
  if n == 0 : a
  else
    fib_iter(n - 1, a + b, a)
  end
end

这是在我机器上运行求fib(10)的结果，当求fib(100)的时候，已经慢得让我无法忍受了。

ruby 代码

require 'benchmark'
include Benchmark

bmbm(12) do |x|
  x.report("fib") { 1000.times { fib(10) } }
  x.report("fib_iter") { 1000.times { fib_iter(10) } }
end

                 user           system       total           real
fib             0.265000   0.000000   0.265000 (  0.266000)
fib_iter      0.016000   0.000000   0.016000 (  0.016000)

    造 成这么大的差异的原因很大一部分是因为重复计算，例如求fib(10)的时候会求解fib(9) + fib(8)，然后求解fib(9)的时候仍然会再次求解fib(8)。当然这里有不少方法来提高树形递归的效率，但是其相对于线性递归的效率低下也是不 争的事实。这并不表明树形递归无用，在有些场合尤其是层次性数据的时候，非常有效。应为这种特殊场合比较难用线性递归或循环来处理，你需要懂懂脑子才能 （也许就想不出）办法把树形递归转换为线性递归或者循环处理。这里又不得不提性能，虽然我极力回避这个问题，但性能终究是一个问题。它使得你的程序运行的不那么好！

分享到：

设计模式学习小结

• 2007-07-01 20:59
• 浏览 3209
• 评论(3)
• 论坛回复 / 浏览 (2 / 5696)
• 查看更多

评论

3 楼 leon_a 2007-07-02  

以前是只知其然而不知其所以然，今天受教了

2 楼 dennis_zane 2007-07-02  

呵呵，我怎么看着眼熟，就是sicp书中概念的ruby版本解释嘛，总结的很好

1 楼 Joard 2007-07-01  

然而它工作得不够好！
    上面说的那些“废话”就是递归的全部了吗？不，很遗憾，递归还有更多的东西。
    通常意义上递归会有结束条件。所谓结束条件就是告诉程序以及到达本次递归的最底层了，不必继续运行的条件。递归至少要包括一个结束条件，而且要确保程序能最终能到达某一个结束条件。不然的话，你的递归程序会因栈空间不足而中止（好吧，我承认也会因内存不足而中止）。 递归的主要开销还是在于函数调用和为了维护执行顺序所保存的中间状态，而这些信息又大多保存在栈空间中。
   “不忙，等着。你刚才不说迭代计算过程是用用固定个数的状态变量吗？”
   对，即便是迭代计算过程的递归它仍然会是消耗正比于函数调用次数的内存空间，而不是常量空间。于是聪明的cs牛人们试图找到解决这一缺陷的办法。

尾递归
    我一直在考虑是否要提到“尾递归（Tail-recursive）”，最主要的原因是我自己对尾递归也不是很了解，但既然是《粗看递归》，那么不提提尾递归怎么也说不过去。因此斗胆在这里王妄讲一下尾递归。（你看我没有骗你吧！终于到尾递归了）
    为了总能在常量内存空间中执行迭代计算过程，即使这一计算是递归过程描述的，具有这一特性的实现称谓“尾递归”（摘抄自SICP）。但是从我的手里的资料来看还有另一种定义：如果一个调用的返回值被作为该递归调用的值立即返回，那么，这个递归调用就是“尾递归”。前者更重实现，而后者侧重形式。在这里让我们回到sum_iter方法，还记得我在那里说其是尾递归写法吗？结合到这里的尾递归定义你也许能明白了吧！但这里要小心，即便是该语言不支持尾递归，sum_iter也仍然可以叫做尾
递归函数（这里是侧重尾递归这种代码形式）。这里又要罗嗦到Tail-call，什么是Tall-call，下面的方法就是区别
java 代码

   1. int inc(int a) { 
   2.     return a++ 
   3. } 
   4.  
   5. int TailCall(){            //尾调用
   6.     int a = 2; 
   7.    return inc(a); 
   8. } 
   9.  
  10. int NotTailCall(){          // 不是尾调用，因为它还要在inc返回後执行加一操作
  11.    int a = 2; 
  12.    return 1 + inc(a); 
  13. } 


综上所述，这些概念还是比较容易区分的。
    关于尾递归的实现，我们还是拿sum_iter来说事，当程序的控制权传递给尾部的sum_iter的时候，前一个sum_iter的栈空间其实已经没有用了，我们可以设法在调用下一个sum_iter的时候用下一个栈结构覆盖当前sum_iter的栈结构，并使得它们的返回值保持一致。总之，尾递归能提高拥有迭代计算过程的递归的效率，但递归计算过程却享受不了了。在下次你看见某个语言里面居然没有提供循环结构的时候，请不要惊讶，“哦，原来是尾递归”。
    像Lisp，（Erlang也支持尾递归）等函数语言里面是实现了“尾递归”的（尾递归的第一种定义）。但是很多语言并没有提供这种削除拥有迭代计算过程的递归调用的所产生的无用栈结构的特性。那么java提供尾递归吗？Eric Allen提供了一中测试方法来测试你的jvm，更准确的说是jit是否提供一定程度上的尾递归。Allen的测试代码如下
java 代码

   1. public class TailRecursionTest { 
   2.   private static int loop(int i) { 
   3.     return loop(i); 
   4.   } 
   5.   public static void main(String[] args) { 
   6.     loop(0); 
   7.   } 
   8. } 


如果jit把这个递归转换成迭代，那么这个程序会一直执行下去，并占用常量空间。如果不支持的话，那么你的程序最终会得到一个 java.lang.StackOverflowError。在SUN的Hotspot JVM上没有提供这种转换，而IBM的JVM上，该程序会稳定一直执行下去。（关于这点我没有考证，应为我没有IBM的JVM）

写在最后
谢谢各位看我罗嗦了这么久，如果你认为这文章太无聊太差劲了，但你又想获得一个更简洁但更准确的关于递归的描述。请参阅SICP的 1.2.1节和1.2.2节，你能通过这个链接看到http://mitpress.mit.edu/sicp/full-text/book/book -Z-H-11.html#%_sec_1.2.1
本文很多地方都是在再“抄袭”该书的观点，请多包含。

如果你对Recursive Function的理论感兴趣可以参考《Type Systems for Programming Languages》。
最后，如果你对尾递归的实现很感兴趣，可以阅读这篇文章http://www.ibm.com/developerworks/cn/linux/l-recurs.html该文简单地描述了在汇编级别来实现尾递归的方法。