【新手进阶】之七：递归算法

roych · 发表于 2012-3-10 11:43:50

   在谈递归算法之前，不得不提的是斐波纳契（Fibonacci）数列。生于十二世纪的斐波纳契（Leonardo Fibonacci）曾提到这样一个问题：有一对兔子，如果每个月生一对小兔子，而刚生下来的兔子两个月后同样每个月生一对小兔子，那么，一对兔子一年内总共能生下几对兔子？
   1……第一个月
   1……第二个月
   2……第三个月，产下第一只兔子（仔兔的第一个月）。
   3……第四个月，产下第二只兔子（仔兔的第二个月）。
   5……第五个月，产下第三只兔子，仔兔产下第一只兔子（仔兔的第三个月）。
   ……………………………………………………………………
   于是得到这样一个数列：1,1,2,3,5,8,13,21……这在数学上解法很多，通项公式是：an=(1/√5)*{[(1+√5)/2]^n - [(1-√5)/2]^n}，并由此引出了黄金比例等等。当我们把通项公式写成程序则得到以下函数：

Function GetF(N As Long)
GetF = (Sqr(5) / 5) * (((1 + Sqr(5)) / 2) ^ N - ((1 - Sqr(5)) / 2) ^ N)
End Function

复制代码

我们需要获取具体值（例如a5）时，就可以直接调用了：

Sub Test()
Debug.Print GetF(5)
End Sub

复制代码

显然，数学不太好的盆友们，一时间未必能推导出通项公式，可如果恰好需要去完成这项任务，该怎么办呢？我们只能使用反推法：从数列中可以看得出来，后一项是前面两项之和。先得到最后一项，再得到倒数第二和倒数第三项，然后再继续往前推，直至得到第一项和第二项。于是整个结果就出来了。
这就是程序上最常用的递归思想。现在我们开始写函数：

Function Fibonacci(N As Long)
If N = 1 Or N = 2 Then Fibonacci = 1
If N >= 3 Then Fibonacci = Fibonacci(N - 1) + Fibonacci(N - 2)
End Function

复制代码

这显然比用通项公式解答起来简单多了。以N=4时为例，运行过程大体如下：
   Fibonacci（4）→Fibonacci（3）+Fibonacci（2）→Fibonacci（2）+Fibonacci（1）+Fibonacci（2）→1+1+1=3
   记得前些日子ycxchen提及，在Access中这些是如何应用的。其实这个算法在Access里也是可以用得上的，常见于树控件中。Kangking同志曾在《程序界面兼工具栏、树、状态栏、页标签及进度条等控件的应用》里就用过它来展开子节点，有兴趣的版友可以去看看。
   这里给一个比较简单的作业，用递归思想写一个阶乘的函数。

游客，如果您要查看本帖隐藏内容请回复

cclxf · 发表于 2021-8-10 09:32:11

学习学习！

heqing3000 · 发表于 2020-4-29 09:36:28

:):):):):):):):):)

XH8608208 · 发表于 2019-4-27 15:52:12

学习学习

hxx3970 · 发表于 2018-9-12 13:11:36

学习一下

ej1213 · 发表于 2018-6-8 16:56:56

学习

miaoiyangzhi · 发表于 2017-3-21 11:30:17

66666学习

72310 · 发表于 2017-2-27 16:48:50

新手回复

anttsy · 发表于 2017-2-22 13:29:23

111111111

wenbin_zheng · 发表于 2017-2-11 14:08:30

学习

帐号		自动登录	找回密码
密码			注册

群介绍
Access培训群 (792054000)
Access免费培训群2 (792054000)
Access经典源码培训群 (77130759)
Access源码技巧群 (138920637)
access vba (307776555)

主题相关群

地区相关群[您还没设置居住地]

[模块/函数] 【新手进阶】之七：递归算法

本帖被以下淘专辑推荐:

群介绍
主题无相 (随机显示版	同地区群块其他地区)