递归（基础教程）

hyqzzs

自己摸索了两个月，才终于发现宝贝，谢谢高手费心，写出如此详细的教程。{:soso_e156:}

Kelidai

要做个记号。

~游戏来了~

彭希仁 发表于 2007-1-25 11:17
Public arr1, j As Long, z%, k%Public arr3(1 To 65536, 1 To 1) As StringSub peng()     ...

  xi i + 1, x, y       '调用自已进行递归      
请教楼主这句是什么意思？ 赋值？还是别的？   xi 的值在变化吗？  

robertliu2013

太好了，感谢楼主分享！

663973866

彭希仁 发表于 2007-1-23 14:05
再看斐波那契数列一例。
                                公元1202年欧洲数学家伦纳德·斐波那契在他所著的《珠算的书》（Liber Abbaci ...

斐波那契数列计算到n为30的时候就开始变慢了 请问有什么解决的方案嘛~

EXCEL江湖

彭希仁 发表于 2007-1-25 11:17
Public arr1, j As Long, z%, k%Public arr3(1 To 65536, 1 To 1) As StringSub peng()     ...

好的学习资料！收藏！

下标越界

663973866 发表于 2014-11-13 16:22
斐波那契数列计算到n为30的时候就开始变慢了 请问有什么解决的方案嘛~

我的电脑上也是差不多到n=30就慢了，到n=40，已经达到6分钟。
使用循环代替递归，n=40,仅0.2秒不到。
下面是我的代码：

1. Function fblq(n&, a)  '递归版
   
2. ' Dim arr&(n)
   
3.   Static a1
   
4.   a1 = a1 + 1
   
5.     If n <= 2 Then
   
6.       fblq = 1
   
7.     Else:
   
8.       fblq = fblq(n - 2, a) + fblq(n - 1, a)
   
9.     End If
   
10.    a(0) = a1
    
11. '   fblq = arr(n)
    
12. End Function
    
13. 
    
14. Sub 测试斐波拉契数列()
    
15. 
    
16. Dim i&, r, c, tim1, tim2, a()
    
17. ReDim a(1)
    
18. tim1 = Timer
    
19. For i = 1 To 40
    
20. Cells(Int((i - 1) / 10) + 3, (i - 1) Mod 10 + 1) = fblq(i, a)
    
21. Next i
    
22. tim2 = Timer
    
23. 
    
24. Cells(1, 2) = tim2 - tim1
    
25. Cells(2, 2) = a(0)
    
26. End Sub
    
27. 
    
28. 
    
29. Function fblq2(n%, a) As Double   '循环版
    
30.   Dim arr() As Double
    
31.   ReDim arr(n)
    
32. ' Static a1
    
33. Dim i
    
34. 
    
35.   'a1 = a1 + 1
    
36.     If n <= 2 Then
    
37.       arr(n) = 1
    
38.     Else:
    
39.       arr(1) = 1
    
40.       arr(2) = 1
    
41. 
    
42.       For i = 3 To n
    
43.       a = a + 1
    
44.       arr(i) = arr(i - 2) + arr(i - 1)
    
45.       Next i
    
46.     End If
    
47.    
    
48.    fblq2 = arr(n)
    
49. End Function
    
50. 
    
51. Sub 测试斐波拉契数列2()
    
52. 
    
53. Dim i%, r, c, tim1, tim2, a
    
54. 
    
55. 
    
56. tim1 = Timer
    
57. For i = 1 To 40
    
58. a = 0
    
59. Cells(Int((i - 1) / 10) + 8, (i - 1) Mod 10 + 1) = fblq2(i, a)
    
60. Cells(Int((i - 1) / 10) + 18, (i - 1) Mod 10 + 1) = a
    
61. 
    
62. 
    
63. Next i
    
64. 
    
65. 
    
66. tim2 = Timer
    
67. 
    
68. Cells(1, 1) = tim2 - tim1
    
69. 
    
70. 
    
71. End Sub
    

复制代码

香川群子

下标越界 发表于 2015-3-16 23:28
我的电脑上也是差不多到n=30就慢了，到n=40，已经达到6分钟。
使用循环代替递归，n=40,仅0.2秒不到。
下 ...

你的代码可以大大简化：

首先，递归的代码：

1. Function Fibo(n%) '斐波那契数 递归计算
   
2.     If n > 1 Then Fibo = Fibo(n - 1) + Fibo(n - 2) Else If n Then Fibo = 1
   
3. End Function
   

复制代码

这是If 结构的横向写法。

如果按照If结构展开，则可以是：
    If n > 1 Then
        Fibo = Fibo(n - 1) + Fibo(n - 2)
    Else 'If n = 1 Or n = 0 Then
        If n Then Fibo = 1 'Else If n = 0 Then Fibo = 0
    End If
蓝色部分是可以省略的。

如果不省略（便于理解）则成为：
    If n > 1 Then
        Fibo = Fibo(n - 1) + Fibo(n - 2)
    ElseIf n = 1 Or n = 0 Then
        If n = 1 Then '可以省略为If n Then
            Fibo = 1
        ElseIf n = 0 Then
            Fibo = 0 '因为Fibo初始值=0所以只一句也可以省略
        End If
    End If

红色部分和蓝色部分，都是可以省略的。
实际上运行效果是完全一致的。

所以，我的递归代码最简洁，只需一句代码：
If n > 1 Then Fibo = Fibo(n - 1) + Fibo(n - 2) Else If n Then Fibo = 1

呵呵。

…………
补充解释，为什么递归计算n较大时(n>30)时会比较慢呢？

因为每一次递归过程都需要递减到n=1和n=0时才能结束，
例如，n=30时，
总的递归次数达到了： 2,692,537次，
其中n=1 递归了：832,040次，
n=0 递归了：514,229次

所以，计算速度会越来越慢！

香川群子

下标越界 发表于 2015-3-16 23:28
我的电脑上也是差不多到n=30就慢了，到n=40，已经达到6分钟。
使用循环代替递归，n=40,仅0.2秒不到。
下 ...

而一般循环计算代码，也可大大简化，无需使用数组。

1. Function Fib(n%) '斐波那契数 循环算法
   
2.     t = 0: t1 = 1
   
3.     For i = 2 To n
   
4.         t2 = t + t1
   
5.         t = t1: t1 = t2
   
6.     Next
   
7.     Fib = t1
   
8. End Function

复制代码

n>46时 计算结果>Long限制

…………
或者使用数组记录1-n全部计算结果时：

1. Function Fib2(n%) '斐波那契数 返回数组结果
   
2.     ReDim a(n)
   
3.     a(1) = 1
   
4.     For i = 2 To n
   
5.         a(i) = a(i - 1) + a(i - 2)
   
6.     Next
   
7.     Fib2 = a
   
8. End Function

复制代码

测试代码为：
Sub test()
    MsgBox Join(Fib2(50), vbCr)
End Sub

计算1-50并输出列表。

下标越界

香川群子 发表于 2015-3-17 08:48
你的代码可以大大简化：

首先，递归的代码：这是If 结构的横向写法。

n=30时，调用函数的次数是1664079次。n=1,2,3……30的次数总和是4356586次。