归去来兮－－漫谈递归

qee用

12．递归转化为循环
  通过对栈的了解，我们已经知道了递归的工作机制，“栈”数据结构的构造，已经为递归程序转化成循环程序解决了技术手段。我们还是来看“阶乘”的例子：
Function Nx2(n)
  If n = 1 Then Nx2 = 1: Exit Function
  Nx2 = n * Nx2(n - 1)
End Function
  转换的分析过程如下：
（1）根据上节的分析，知道需要入栈的数据为n个，设定数组arr(1 to n)，指针变量sp（初始值为0）。
（2）根据前面对递归结构的了解，在复杂度参数达到“出口”值前，为数据进栈；当达到“出口”值时，发生回归，数据出栈。
（3）为了直观起见，约定使用do/loop循环结构，在栈中数据全部弹出后，循环结束。
  函数Nx2转换循环结构的代码如下：
Function Nx3(n)
  Dim arr%(), sp% ‘定义栈及栈指针
  ReDim arr(1 To n)  ‘栈大小
  sp = 0 ‘栈指针初始化
  Nx3 = 1 ‘乘运算的初始值
  Do
Redo:
    If n = 1 Then ‘判断是否回归,数据出栈
      If sp = 0 Then Exit Do ‘栈已空,结束循环
      Nx3 = Nx3 * arr(sp) ‘弹出数据,返回结果
      sp = sp – 1 ‘栈指针减1
     GoTo Redo
    End If
    sp = sp + 1  ‘栈指针加1
    arr(sp) = n ‘数据入栈
    n = n – 1 ‘准备下一个进栈数据
  Loop
End Function
  朋友们注意了吗，上面“翻译”出的代码和最初用循环写出的Nx1相比已经面目全非了，如果你再好事一点的话，测试的速度比递归程序还要慢25%左右。分析一下原因：
（1）Nx3 是直接根据递归程序翻译来的，它的思路其实仍是被翻译代码的思路；Nx1是按照循环的思路写出的。这是二者不一样的原因。
（2）“阶乘”的递归在进出栈的操作中几乎没有任何多余的操作，VBA编译系统对这种“简单且常见”结构的优化功夫已经做得足够好，而转换的循环代码模拟栈增加的一些操作没有被编译成足够高效的代码（当然也怪我，至少for循环比do循环快吧），且没有进行任何的优化，这是循环反而慢的原因。
  递归转化为循环的另一个例子－“汉诺塔”的代码在前面已经给出了，对照上例大家应该不难理解的，我少费点口舌，其分析转换过程留做思考题吧。
  如果你可以脱离递归的思路去理解Nx3的代码，你会发现，它仍然是可以理解的，是的，使用“栈”思路本身也是一种算法思想，也许你以前听说过，这就是回塑！回塑是和递归结伴而来的，回塑是循环结构的代码，递归是递归结构的代码，这样说不是为了文字本身，前文提过的，现在你应该很清楚地知道了，递归不仅仅是算法，它也是一种代码结构。考证二者谁先谁后也许已经不重要了，回塑算法已经成为独立的算法思想，很多喜欢使用for镶嵌循环但当循环的层次不确定时感觉无从下手的时候，就是回塑算法应用的场合，有兴趣朋友可以看看我曾经写过的一个数独游戏（ “数独”游戏，希望你喜欢 ）。更多的内容，如果有时间，再和朋友们另文探讨。
  关于递归的理论探讨到这儿告一段落，写程序是实践性的，需要多看、多想、多练。下一节－本文的最后一节将为您准备一些典型的递归例，这些例子将使您亲密接触递归的实战技巧。

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

qee用

13．递归实战技巧例
[例1] 递归（基础教程）（彭希仁）
这个贴子建议您仔细地多看几遍。
[例2]组合问题：列出n个数（1-n）中任选r个数的所有组合。
分析：设定用数组arr来保存所有组合结果（每一个结果为用空格隔开的数字，如：“1 2 3 4”），变量q来记录组合个数，根据已经知道的数学知识，q=n!/(r!*(n-r)!)，这样我们就不多次使用redim arr了，计算阶乘的函数我们也已经有了。先来分析递归过程，假定过程名为cmb(n,r)，两个参数为n、r，“基状态”有两个：
（1）当r=1时，可以将1-n分别写入数组。
（2）当n=r时，可以直接将结果（1 2 3…n）写入数组。
 “递归部分”：
考虑从1-n中选r的数，可以分解成两种情况：
（1）当这r个数中有n时，此时可以先求出cmb(n-1,r-1)，然后在cmb(n-1,r-1)的结果中把n加上去就是r个数了。这样的话，我们可以增加一个参数s，传递要求包含的数字(为字符型)，如果没有需要传递的参数s，可以传递空串。
（2）当这r个数中没有n时，此时的结果就是cmb(n-1,r)。
通过分解成这两种情况，降低复杂度的目的就达到了。这样递归代码也就出来了：
Dim arr, q
Sub main()
  Dim n%, r%
  n = 8
  r = 3
  q = 0
  ReDim arr(1 To nx(n) / nx(r) / nx(n - r))
  cmb n, r, ""
  Columns("A").ClearContents
  [a1].Resize(q, 1) = Application.Transpose(arr)
End Sub
Sub cmb(ByVal n As Integer, ByVal r As Integer, ByVal s As String)
  Dim i%
  If r = 1 Then
    For i = 1 To n
    q = q + 1
    arr(q) = i & " " & s
    Next i
    Exit Sub
  ElseIf n = r Then
    q = q + 1
    For i = 1 To n
      arr(q) = arr(q) & i & " "
    Next i
    arr(q) = arr(q) & s
    Exit Sub
  End If
  cmb n - 1, r, s
  cmb n - 1, r - 1, n & " " & s
End Sub
Function nx(n)
  Dim i%
  nx = 1
  For i = 2 To n
    nx = nx * i
  Next i
End Function
[例3]列出指定文件夹及其子文件夹下的所有文件。
分析：
（1）“出口”条件：
当文件夹下没有子文件夹，列出该文件夹下的文件即可。
（2）“递归部分”降阶：
以该文件夹的子文件夹做参数，再次引发递归。
代码见：
http://club.excelhome.net/viewthread.php?tid=206228
[例4]……
事不过三，呵呵，开个玩笑。以后再慢慢补充吧，也欢迎大家把好的代码拿出来分享。

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

qee用

......
0．[题后]
归去来兮！往而返，返而复。不知不觉间懒病复发，还好总算在“竭”之前勉勉强强完成了“递归十三篇”。能力局限，时间仓促，套用一句：大家辩证地参考着看吧。

dnss

多谢分享[em02]

以后还有不明地方,请多多指教.

彭希仁

绝对精华

qee用

QUOTE:

以下是引用彭希仁在2007-2-8 10:28:42的发言：

绝对精华

彭兄过奖了.吸收了你的很多好东西.
一开始构思的时候还有好多,但写到后来就松了,也许算法之类的甚至每一个个例,要讲清楚需要很多口舌,却因每个人的关注点不同而未必有功,写的和看的人都很烦.

冰山上的来客

study

tmd2008

绝对牛B！真佩服之极！如果能学到Qee用一半就不错了！

lyb200

厉害

nawong

看qee用兄的文章，總讓我感覺在看故事，不枯燥，而且總覺得后頭還有好戲。一路跟讀下來，一個字.....爽。謝謝。