归去来兮－－漫谈递归

qee用

0．先礼后兵（代前言）
    礼者，理也；兵者，实战也。本文以此来循序探讨递归，却未必是渐进的，尽管我尽力想做到，如果你看到了无法理解的某些词句，可以先跳过去，作者鼓励你把它做为关键词在IE上搜索，以使这些概念更清晰和全面。本文大体上从递归的一般理论到相关知识，放在最后的是实战技巧。但既谓之漫谈，也不拘泥于此。
我们开始吧。
1．何谓递归？
    通常看到的定义是：当过程（函数）（本文后面将省略上面括号里的内容）直接或间接调用了自己时，则发生了递归。
    直接：入口àAà入口
    间接：入口àAàBà入口
    请原谅我无法用文字把上面的图画得象环型那样直观，第一个是直接调用，即过程A调用了自身，第二个是间接调用，即过程A调用了B，B又调用了A自身。
    令：C为AàB，则上面的间接调用模式变为
    入口àCà入口
    这其实就是直接调用的模式。可以认为，C之所以被分解为两个过程A和B，只是程序为了在步骤上更清晰而已（我们通常不都是这样写代码吗）！笔者首先想告诉你的，不要去节外生枝地管什么直接间接而生涩地记住一个看似周全的定义，本人对“概念”的一贯态度是，能够识别即可，递归就是指过程自己调用自己！
2．递归是算法吗？
    就算是吧。反正大家都这么叫了，存在即合理嘛。程序=数据结构+算法，它总不会是数据结构吧。
    如同所有的事物一样，算法从不同的角度也可以有不同的分类，这种从不同角度进行的分类往往并不是排斥的，清楚这一点，可以使你在看到各种算法的称谓时不会因迷茫而人云亦云。算法分类按照处理的任务，有我们常说的排序算法、查找算法；按照指导思想，有分而治之算法、穷举算法。而所谓递归算法，是指在过程中使用了“自己调用自己”的算法，它是按什么分类的呢？留下这个问题，在后面慢慢体会吧，呵呵。
3．递归是必需掌握的吗？
    不然！程序结构的三元素是顺序、选择、循环，用这三种结构可以完成任何功能的代码。不用我多说吧，所有的程序设计教科书都是这样说的，很多早期的语言甚至不支持递归。让我们回头看一下前面的递归模式，它是不是和“循环”结构很象？是的，所有可用递归完成的代码也都可以用循环来完成，反之亦然。二者的转换方法我们会在后面探讨。

[此贴子已经被作者于2007-1-29 21:14:47编辑过]

qee用

4．递归的效率问题
    搜一下网络资源，说什么的都有，一时本人也没了主章。这个问题的结论留到本文的最后来下。
    先说下我的观点：因为递归过程中，存在着大量的进退栈操作，这种进退栈会吃掉大量的系统资源，同时很多是无谓的操作，因此无论是资源还是时间的效率都比等价的循环要低。以菲波利数列为例，递归的时间复杂度是O(nlogn)，循环是O(n)，显然，当n>2时，即有nlogn>n。在递归技术早期，编译系统是把整个过程都压栈的，随着这项技术逐步研究深入，只需要对局部变量做栈处理，相对有了很大优化。但，总体上效率低的结论不会变。
也许你已经在质疑了：递归已经被你说得一无是处，又那么生涩难懂，还有必要学它吗？！不然，它实在很有用，适用于它的舞台容后道来。
5．递归难吗？
    难者不会，会者不难。
    嘿嘿，等于没说。客观地说，初次接触递归对大多数人，都会有一个从难到易的适应过程。甚至看过并且“理解”了一些递归的代码，仍不敢言易，原因何在呢？
来看一个用递归求解迷宫的思路，迷宫有一个入口和一个出口，从入口进入后，如果遇到了分支，则每一个分支又相当于一个入口…这样就形成了一个递归，由此解题的思路是从入口处派入一支寻路的队伍，当遇到分支时，支队长把这个队伍分成若干个小分队，如此下去，总会有一支分队找到出口，然后再逐级报告它的上一级，这样便会得出迷宫的行走路线。在这里，寻路的开始阶段你不会知道需要一支由多少人组成的寻路队伍，递归就是这样！它假定你有足够的资源来支付未知不确定的帐单。这和我们正常的思维是不同的， 程序是我们让计算机执行我们意图的语言指令，但在日产生活中，我们有使用递归思想让自己或别人去做事的习惯吗？现实中如果真的遇到了迷宫问题，有人会这样做吗？
另一方面，我们需要知道我们的思路和代码是否正确，为什么正确？这就是正确性的证明问题，但遗憾的是，人的思维深度是有限的，两层或三层的递归也许在你的大脑中可以想象出它的完整过程，更多层以后，递归正确性的证明只能使用抽象的方法，但我们通常缺少这种训练。
    回到前面的迷宫问题，仔细地看看（想想）递归的思路，你会发现，如果资源能够得到保证的话，这种思路确实使问题变得简单了！而且一旦你形成了这种思维习惯，你会发现原本很多复杂的问题都变得如此简单！
    到这儿，如果你突然觉得递归简单了，那我也不得不告诉你，别高兴得太早，学会一门技术不会这么简单。

[此贴子已经被作者于2007-1-29 21:16:02编辑过]

qee用

6．神奇的“黑匣子”
    从现在起，稍稍放慢一下阅读的速度，呵呵。
    “黑匣子”是一种抽象的程序设计思想，是面象对象的程序设计思想之一，但事实上，这种思想在面象对象的程序设计理论提出之前早已被广泛应用。它在逻辑上把一个复杂的任务划分为若干相对简单的子任务，然后把子任务当成是“黑匣子”来考虑，即调用程序中只需要为子程序（任务）起一个可以识别的名子（然后通过这个名子进行调用）、需要传递的参数，然后坐享应该得到的结果，而不再去考虑子任务的内部实现细节（对子任务的实现另行独立考虑）。这样的结果是使程序结构更清晰，可读性也更强（这对复杂的任务非常重要）。这样，我们只需要要知道，当使用下句代码时：
    MySubName n
    我们可以确信得到期望的运行结果，而不必去想MySubName的运行过程，这就是“黑匣子”的神奇。这一思想对理解递归至关重要，因为在递归中，MySubName同时也是调用程序自己的名子。
    如果您觉得还有不清楚，不要紧，在稍后的实例中还会作出解释。

[此贴子已经被作者于2007-1-29 21:06:25编辑过]

northwolves

Q兄的文笔如行云流水，读起来也是琅琅上口，比喻得很好。

期待下文.....

qee用

7．第一个经典：阶乘
     所以说经典，是因为几乎所有介绍递归的文章都会提到它，也许阶乘是我们能想到的最简明的事例。先来看一下常规思路（循环）的算法程序：
Function Nx1(n)
  Dim i%
  Nx1 = 1
  For i = 1 To n
    Nx1 = Nx1 * i
  Next i
End Function
    再来看一下用递归的写法：
    函数名：Nx2，参数：n，功能：返回n的阶乘。
Function Nx2(n)
  If n = 1 Then Nx2 = 1: Exit Function
  Nx2 = n * Nx2(n - 1)
End Function
    第二句代码的含义是n的阶乘等于n乘以n-1的阶乘，别忘了我们说过的“黑匣子”—这里既是Nx2！所以不要去想Nx2(n - 1)是怎么样的计算过程啦。经典吧哈？这段代码的经典还在于：它包含了一般递归程序的所有要素。来描述一下：
（1）递归程序至少要有一个出口条件，已使得程序能够停止下来。这个出口条件又被称为“基状态”，在“基状态”下，结果可以直接被表述。如上例的第一句“If n = 1 Then Nx2 = 1: Exit Function”。
（2）递归程序要有递归部分，我们设参数n通常表示问题的复杂度，n=1表示“基状态”，递归部分需要完成的是：
a．将复杂度为n的问题转化为低复杂度n-1，使它向复杂度为1的“基状态”问题逼近。
b．完成上述转换中n层和n-1层的衔接处理。这种衔接可以是数学关系，如本例“n*”，也可以不是。
程序员要做的就是将可用递归解决的问题按照上述逻辑部分归纳出来，这需要在实战中增长经验。对初次接触的朋友需要补充的是，上面两部分划分只是抽象的表述，这意味着实际递归问题的复杂度通常不是用一个参数表示，“基状态”也可以不是数字1，低复杂度n-1的参数不是比低复杂度n的参数小，甚至不是数字关系。
（3）由于大多数递归程序是使用参数来描述复杂度，并且在递归部分需要降低复杂度，所以一般情况下，递归程序是作为子程序被调用，而不能独立运行。在调用递归程序的程序中需要初始化复杂度参数，即所谓“种子”。
我不排除你可以构思出一些不使用参数并且可以自启动的递归程序，但那只属于例外，而且也违背递归的本意。
（4）递归程序与循环程序相比，显得简洁，正如你所看到的。而且你一旦熟悉了这种模式，它更易读，这在复杂的问题上会表现地更明显。
本节的最后，也不得不说说，对这个经典程序的有关批评的声音，因为阶乘的定义从来就是：n!=1ⅹ2ⅹ…ⅹn。所以使用循环的方法更容易被理解和接受，而且也说不上繁琐！算法是为了实用的，而不是为了“经典”，在这里我们没有看到使用递归的任何必要性和优势，很多通过这个实例接触递归的人从此形成了对递归根深蒂固的评价：一个花架子而已！并永远忽略了递归。这就是很多高手不研究递归的原因吧。下一个经典将改变您的这种认识。
附：循环与递归阶乘算法性能比较的测试代码（具体函数代码见上）：
Sub TestNx()
  Dim i&
  Dim k1#, k2#
  Dim t1, t2, t3
  Const n = 100
  Const Runtimes = 10000
  t1 = Timer
  For i = 1 To Runtimes
    k1 = Nx1(n)
  Next i
  t2 = Timer
  For i = 1 To Runtimes
    k2 = Nx2(n)
  Next i
  t3 = Timer
  Debug.Print k1, k2
  Debug.Print t2 - t1, t3 - t2
End Sub

[此贴子已经被作者于2007-1-29 21:10:31编辑过]

qee用

8．第二个经典：汉诺塔
    也许您已经想到了，真正令人信服的递归经典，是汉诺塔问题，请参考 递归（基础教程）（彭希仁）2，3两楼。为了本文的完整，我需要重复一下。
    问题：有A、B、C共3根针，其中A针从上到下按从小到大的顺序串上了N个金片。要求把金片全部移动到C针上去，可以借助B针，但每次只能移动一片，且移动过程中任何一根针的金片都保持从小到大的顺序。
    使用递归的解题思路是：注意到要把n片金片从A移到C，只要把上面的（n－1）个金片搬到B针上，然后把最底下的金片就可以直接从A移到C。这样问题就可转化为把（n－1）个金片从B搬到C针上（金片n搬到C后就不必移动了）。直至使问题转化为搬动1个金片的问题。
    下面是按照上面思路写出的VBA代码：
    在递归外部增加了一个数组arr1用来保存求解过程，变量q是求解需要的步骤数量。
Dim arr1, arr2, q
Private Sub Hanoi1(ByVal N%, ByVal A$, ByVal B$, ByVal C$)
'“A → C” 来代表把金片从A针移动到C针,即1阶汉诺塔问题的解
  If N = 1 Then
    q = q + 1: arr1(q) = A & "→" & C '把金片n从A移动到C
  Else
    Hanoi1 N - 1, A, C, B 'n-1个金片从A到B，以C为过渡
    q = q + 1: arr1(q) = A & "→" & C '把金片n从A移动到C
    Hanoi1 N - 1, B, A, C 'n-1个金片从B到C，以A为过渡
  End If
End Sub
    一个看似如此复杂的问题，就这样解决了，竟然只需要寥寥几行代码！有人说汉诺塔问题是不得不使用递归的典型，的确如此，在相当长的时间内，它是唯一的思路。我知道你要说那个美国营养师的解法，但那个思路相比递归的解法，要难懂得多，而且，我相信那是对递归的结果进行再归纳才形成的（呵呵，你别想说服我，我坚持）。
    不错，我们可以使用循环来完成上述功能，但这种转换只是形式上的（不要着急知道转换的方法，我们后文再谈），它的思想仍然是递归的思想。思路和代码形式的不统一，对程序员实在是很大的痛苦，因为转换后几乎已经没有了可读性，不要说再需要维护和修改了。
    看来是需要说说递归的好了，当计算机硬件的超快速发展使内存和速度都不再成为障碍的时候，可以如此简明高效地解决问题，我们还要拒绝递归吗？编译系统开发人员对递归的优化研究也从未停止过，而且已经成果不菲，对这方面的讨论已超出本文的范围，有兴趣的朋友可以参考有关著述，如果我们可以更天真一点去想象的话，也许有一天，编译系统会使递归的代码效率和使用冗长代码写出的循环代码相比，一点也不逊色！

[此贴子已经被作者于2007-1-29 21:18:48编辑过]

qee用

附：循环与递归汉诺塔算法性能比较的测试代码
Dim arr1, arr2, q
Sub TestHanoi()
  Dim t1, t2, t3
  Dim i%
  Const RunTimes = 100
  Const N = 10
  ‘N个金片需要的步骤数为2 ^ N – 1
  ‘arr1存放递归算法结果，arr2存放循环算法计算的结果
  ReDim arr1(1 To 2 ^ N - 1), arr2(1 To 2 ^ N - 1)
  t1 = Timer
  For i = 1 To RunTimes
  q = 0
  Hanoi1 N, "A", "B", "C"
  Next i
  t2 = Timer
  For i = 1 To RunTimes
  q = 0
  Hanoi2 N, "A", "B", "C"
  Next i
  t3 = Timer
  Debug.Print t2 - t1, t3 - t2
  Range("A:B").ClearContents
  [a1].Resize(q, 1) = Application.Transpose(arr1)
  [b1].Resize(q, 1) = Application.Transpose(arr2)
End Sub
Private Sub Hanoi1(ByVal N%, ByVal A$, ByVal B$, ByVal C$)
  If N = 1 Then
    q = q + 1: arr1(q) = A & "→" & C
  Else
    Hanoi1 N - 1, A, C, B
    q = q + 1: arr1(q) = A & "→" & C
    Hanoi1 N - 1, B, A, C
  End If
End Sub
Private Sub Hanoi2(ByVal N%, ByVal A$, ByVal B$, ByVal C$)
 ‘根据递归代码写出的循环代码
  Dim s$(1 To 3)
  Dim i%, j%, k%, m%, p%, qa%
  ReDim ia(1 To N), ja(1 To N), ka(1 To N), pa(1 To N)
  s(1) = A
  s(2) = B
  s(3) = C
  i = 1
  j = 2
  k = 3
  p = N
  Do
star:
    If p = 1 Then
      q = q + 1
      arr2(q) = s(i) & "→" & s(k)
      If qa <= 0 Then Exit Do
      p = pa(qa)
      i = ia(qa)
      j = ja(qa)
      k = ka(qa)
      q = q + 1
      arr2(q) = s(i) & "→" & s(k)
      qa = qa - 1
      m = i
      i = j
      j = m
      GoTo star
    End If
    p = p - 1
    qa = qa + 1
    pa(qa) = p
    ia(qa) = i
    ja(qa) = j
    ka(qa) = k
    m = j
    j = k
    k = m
  Loop
End Sub

[此贴子已经被作者于2007-1-29 21:20:34编辑过]

qee用

9．归纳的步骤
    从众多的个性问题抽象出一般的表述，即谓归纳，虽然归纳不是递归独有的方法，但没有哪种算法象递归这样依赖这种思想。递归设计的全部过程就是将可用递归方法解决的问题归纳成通用的、一般的递归模式并据此写出相应的代码。我们无法说到每一个问题，万紫千红的美妙需要您在未来的探索路上慢慢体味。本文帮您解决三方面的问题，一是归纳出递归的基本特征，这在第一个经典中已经完成；二是给您一些常见问题的演示，这部分放在后面完成；三就是本节要告诉您的完成这个过程的一般步骤，这些步骤可以保证您正确地做事。
（1）判断问题是否属于递归问题，如果问题可以划分为多次相似的操作即为递归问题。
（2）确定任务的目标和需要的参数。任务是指重复的相似操作，如果目标是产生一个确定的计算结果，通常使用Function构造，如果是产生一系列结果或对特定目标的操作，一般使用Sub来完成。参数包括对问题复杂度进行表达的变量，也包括在两级递归中需要传递的数值。
（3）确定递归程序的内部变量和外部变量。对需要输出一组结果的，为使结果不受递归过程的影响，通常使用外部变量或外部对象。
    需要说明的，对变量是使用参数还是使用外部变量或者其它可以保存数据的外部对象（如工作表），应以代码的清晰易读为原则。应尽量避免使用Static类型的变量或函数，虽然它可以使原本需要外部的变量巧妙地转化为内部变量，但通常情况下理解Static要麻烦地多，这不符合使用递归的出发点。
（4）选定“基状态”（或出口），并确定在“基状态”下应完成的任务。对可用数值参数表示复杂度的问题，“基状态”应选择某个参数的极值（最大值或最小值）。需要注意的是，“基状态”并不一定只是一种状态，有时是多种可能的状态。与“基状态”对应的一端即是后面启动递归的“种子”。
（5）确定本递归层应完成的工作和与相邻层的衔接工作，以及以何种方式降低复杂度并引发递归过程。
（6）在调用程序中初始化“种子”值，并保证有关环境变量设定为应有状态，调用递归程序。
    看到这儿，有些朋友已经开始头大了吧。其实你不要太在意现在理解或记住了多少，这些步骤在实际应用中可能会有一些细小的差异。我的建议是慢慢地培养遵循这些步骤的习惯在学习递归的初期是必要，或者你可以对照上述步骤去分析你手头的递归例子。

[此贴子已经被作者于2007-1-31 10:39:44编辑过]

qee用

10．循环转化为递归
    循环结构内部执行的都是相同的任务，所以它一定可以使用递归的结构完成。来看一段简单的代码：
Sub abc1()
  Dim i%
  For i = 1 To 10
    Cells(i, 3) = Cells(i, 1) + Cells(i, 2)
  Next i
End Sub
    上面这段代码完成的任务是从第1行到第10行，计算第1列与第2列的和写入第3列。对照前面提到的步骤分析如下：
（1）参数为行i,取过程名称为abc2
Sub abc2(ByVal i As Integer)
（2）出口i>11（种子为1）
  If i > 10 Then Exit Sub
（3）本层次要完成的任务为
  Cells(i, 3) = Cells(i, 1) + Cells(i, 2)
    和相邻层没有衔接关系，也不需要做其它工作，直接引发下层，过程结束
abc2 i + 1
end sub
    将上面得到的代码连起来：
Sub abc2(ByVal i As Integer)
  If i > 10 Then Exit Sub
  Cells(i, 3) = Cells(i, 1) + Cells(i, 2)
  abc2 i + 1
End Sub
（4）在调用过程中用初始值启动递归过程。
Sub cabc()
 abc2 1
End Sub
    对两层以上的循环，可以先将最内层的循环作为一个递归过程，将它外层的循环当做调用过程，然后逐层进行递归化，也可以将各层循环看作参数，按照一层循环的方法进行转化。下面是使用后一种方法对两层循环转化的例子：
循环程序：
Sub abc3()
  Dim i%, j%
  For i = 1 To 3
    For j = 1 To 5
      Cells(i, j) = i * j
    Next j
  Next i
End Sub
转化的递归程序（分析步骤同上）：
Sub abc4(ByVal i As Integer, ByVal j As Integer)
  If i > 3 Then Exit Sub
  Cells(i, j) = i * j
  If j = 5 Then
    abc4 i + 1, 1
  Else
    abc4 i, j + 1
  End If
End Sub
Sub callabc4()
  abc4 1, 1
End Sub
    也许上面的转化，包括后面要说的递归转化为循环，除了给前面说过的结论以实证外，并不一定有太多的现实意义，但起码让我们知道，想到了其中的一种方式，同时还有另一种方式的存在，如果你有兴趣从各自的立场去理解这两种方式的话，可以加深对它们的理解。也正因如此，我们通常并不局限于使用一种方式，是选择递归还是循环抑或两者共用，应统筹考虑程序的可读性和效率。接下来要探讨递归转化为循环的方法，在此之前，先来了解一个重要的相关知识。

[此贴子已经被作者于2007-1-31 10:41:47编辑过]

qee用

11．栈
  提到栈，总让人想到汇编等低级语言（请不要和数据结构中的“栈”相混淆，后面我们还要说到），它是指在内存中开辟的一端固定一端活动的存储空间，固定端称为栈底，活动端称为栈顶，CPU中有一个叫SP的指针寄存器，始终指向栈顶，数据在栈中的存储遵循后进先出的原则，栈的作用之一就是在发生子程序调用时进行数据的现场保护，调用前，系统会将调用地址、局部变量等压入栈中，调用完成后再从栈中弹出这些数据以使程序继续向下运行。在VBA和其它的高级语言中，栈的操作是由编译系统自动完成的，并不需要程序员的额外干涉。前面已经说过，递归的过程其实就是栈的工作过程，虽然本文前面给出了一个“黑匣子”理论去理解递归，但多数朋友一定还挂着问号吧，至少那样理解感觉上有点强词夺理的样子，抽象地有点让人不放心，正因为这样，“正面”地从栈的工作过程去跟踪和理解递归的工作过程对学习递归是有必要的。来看一下“阶乘”的例子：
Function Nx2(n)
  If n = 1 Then Nx2 = 1: Exit Function
  Nx2 = n * Nx2(n - 1)
End Function
假定n=3，即要计算Nx2(3)
开始时，栈中数据为：空
第1步：
n=3 因不符合第一行代码的出口条件，第二行代码需要递归，所以将n(3)进栈，调用Nx2(n - 1)即Nx2(2)
此时栈中数据为：3
第2步：
n=2 因不符合第一行代码的出口条件，第二行代码需要递归，所以将n(2)进栈，调用Nx2(n - 1) 即Nx2(1)
此时栈中数据为：3，2
第3步：
n=1 因符合第一行代码的出口条件，返回Nx2(1)的值1
此时栈中数据为：3，2
第4步：
n=2 从栈中弹出数据2，与返回的Nx2(1)的值1相乘，返回Nx2(2)的值2
此时栈中数据为：3
第5步：
n=3 从栈中弹出数据3，与返回的Nx2(2)的值2相乘，返回Nx2(3)的值6
此时栈中数据为：空
  递归过程完成。上面1-3步通常称为递推过程（有点向下级推卸责任的味道），4-5称为回归过程（回收下属的劳动成果）。
  可惜我不会做Flash，无法给出最直观的示意，麻烦您多看几遍吧，应该还是可以理解的。
  现在来说说数据结构中的“栈”，它是指按照栈的特点构造的“链表”式数据，在VBA中，实现“栈”的简单方法是使用一个数组变量和一个单独的整型变量，数组用来存储数据，数组的下界即栈底，上界为栈顶，单独的变量用作“指针寄存器”，记录栈顶的位置，进栈时，栈顶值增加1，弹出数据时，栈顶值减少1。实例将在下节给出。

[此贴子已经被作者于2007-2-7 22:05:19编辑过]