递归（基础教程）

香川群子

下标越界 发表于 2015-3-17 14:31
n=30时，调用函数的次数是1664079次。n=1,2,3……30的次数总和是4356586次。

呵呵，逻辑上正确的递归代码应该是：

If n > 1 Then Fib = Fib(n - 1) + Fib(n - 2) Else If n Then Fib = 1

因此n=30时，需调用递归过程 2692537次。

而我一开始给出的递归代码是：
If n > 2 Then Fib = Fib(n - 1) + Fib(n - 2) Else If n Then Fib = 1

这个在算法逻辑上讲是有问题的，但从实际效果上来看却仍然是正确的……误打误撞而已。
因为 n=2时，碰巧结果=1 所以没有导致错误而已。

但这么用的话，显然可以节省很多次的递归过程了。
所以，最后结果递归次数只有=1664079次了。

…………
其实，我前面的回帖已经更正为 n > 1 。

下标越界

香川群子 发表于 2015-3-17 16:44
呵呵，逻辑上正确的递归代码应该是：

If n > 1 Then Fib = Fib(n - 1) + Fib(n - 2) Else If n Then F ...

    群子说得很对。群子的代码n=30时，调用次数确实是2692537次。
    倒是我对顺序语句及静态变量static的在顺序语句中使用位置没有仔细考虑，笼统地认为只要放在Fibo函数中就OK了。现在看来其实不然。
    以下是我的测试代码：

1. Function Fibo(n%, arr) '香川群子版 斐波那契数 递归计算
   
2.   Static a&
   
3.    
   
4.    
   
5. 
   
6.     If n > 1 Then Fibo = Fibo(n - 1, arr) + Fibo(n - 2, arr) Else If n Then Fibo = 1
   
7.    
   
8.     a = a + 1
   
9.     arr(n) = a
   
10.    
    
11. End Function
    
12. Sub 测试香川版斐波拉契数递归计算()
    
13. Dim i%, r, c, tim1, tim2, nrec(), nCount(), n%
    
14. Static nStart&
    
15. n = 30
    
16. 
    
17. ReDim nrec(n), nCount(n)
    
18. 
    
19. 
    
20. 
    
21. 
    
22. Rows.Clear
    
23. 
    
24. i = 1
    
25. 
    
26. tim1 = Timer
    
27. Do While i <= 30
    
28. Cells(Int((i - 1) / 10) + 3, (i - 1) Mod 10 + 1) = Fibo(i, nrec)
    
29. nrec(i) = nrec(i) - nStart
    
30. 
    
31. Cells(Int((i - 1) / 10) + 11, (i - 1) Mod 10 + 1) = nrec(i)
    
32. 
    
33. 
    
34. nCount(i) = nrec(i)
    
35. Cells(Int((i - 1) / 10) + 19, (i - 1) Mod 10 + 1) = nCount(i) - nCount(i - 1)
    
36. i = i + 1
    
37. Loop
    
38. tim2 = Timer
    
39. 
    
40. nStart = nStart + nrec(n)
    
41. MsgBox nStart
    
42. Cells(1, 1) = tim2 - tim1
    
43. Range("A2") = "F(1)、F(2)、……、F(30)"
    
44. Range("A10") = "计算F(1)、F(2)、……、F(30)调用递归函数次数总和"
    
45. Range("A18") = "计算F(n)调用递归函数次数"
    
46. 
    
47. 
    
48. End Sub

复制代码

下标越界

群子可能以为我使用静态变量做计数器对
If n > 2 Then Fibo = Fibo(n - 1, arr) + Fibo(n - 2, arr) Else If n Then Fibo = 1
作了n=30的调用次数测试（正巧群子在编辑回帖时曾首发语句是该句），所以才测试出n=30时，调用次数是1664079次。

其实我看到的是群子已经修改后的这句：
If n > 1 Then Fibo = Fibo(n - 1, arr) + Fibo(n - 2, arr) Else If n Then Fibo = 1
但在加入静态变量计数器时，语句位置放在该句的前面，即：
Static a&

    a = a + 1
    arr(n) = a

  If n > 1 Then Fibo = Fibo(n - 1, arr) + Fibo(n - 2, arr) Else If n Then Fibo = 1

于是得出了群子的Fibo函数在n=30时，调用次数仍然是1664079次的错误结果。

现在看来要正确的计次数，静态变量及赋值应该放在 If n > 1 Then Fibo = Fibo(n - 1, arr) + Fibo(n - 2, arr) Else If n Then Fibo = 1后面，即如上面贴出的代码顺序。

   

zhangzhang

Marked............

vested

Long_III 发表于 2007-1-26 10:06
QUOTE:以下是引用彭希仁在2007-1-25 11:17:16的发言：对于数字一来说，也只有0（不出现）和1（出现） 两种 ...

请教版主，如果20个数，不用i=1 to 20 而用 i = 1 to 2怎么用法，不理解？

jsgj2023

虽然不能全部看懂，但是被深深的吸引了。

ydlpc

温故而知新，谢谢帮助打开新视界了

rkmglory

感谢楼主分享，收藏了

Nick_Chen0622

dcw0402 发表于 2010-3-15 19:02
彭版38楼这个迷宫我做了好几天了,也没结果,能否给个答案,头已太大了,救命

[ 本帖最后由 dcw0402 于 2010 ...

老师，请问这个迷宫您解答出来了吗？

fhb197999

留个脚印，到时来学习！