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

roych

       在谈递归算法之前，不得不提的是斐波纳契（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}，并由此引出了黄金比例等等。当我们把通项公式写成程序则得到以下函数：

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

复制代码

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

1. Sub Test()
   
2. Debug.Print GetF(5)
   
3. End Sub

复制代码

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

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

复制代码

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

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

【新手入门】之一：If分支语句
【新手入门】之二：分支语句总结
【新手入门】之三：循环语句For
【新手入门】之四：循环语句Do和死循环
【新手入门】之五：公共变量与传址过程、传值过程
【新手入门】之六：“悲欢离合总无情”——浅谈Split和Join
【新手入门】之七：嵌套与并列——再谈If流程问题
【新手入门】之八：“连就连”——浅谈“&”和“+”连接符的区别
【新手入门】之九：从百钱百鸡谈起——浅谈“规划求解”兼答lingjiang问
【新手入门】之十：书到用时方恨少——自定义菜单（Access 2003）的制作
【新手入门】之十一：浅谈ADO之序言
【新手入门】之十二：浅谈ADO之Connection
【新手入门】之十三：浅谈ADO之Conmmand（上）
【新手入门】之十四：浅谈ADO之Command（下）
【新手入门】之十五：浅谈ADO之Recordset（上）
【新手入门】之十六：浅谈ADO之Recordset（下）
【新手入门】之十七：浅谈列表框的使用
【新手入门】之十八：双击列表框修改数据
【新手入门】之十九：从“书与女友恕不外借”谈起——浅谈“Bookmark”的使用
【新手入门】之二十：“书与书签”——bookmark属性答疑
【新手入门】之二十一：记录集的“凌迟”——逐条导出记录集

【新手进阶】之一：基础算法（一）
【新手进阶】之二：基础算法（二）
【新手进阶】之三：基础算法（三）
【新手进阶】之四：基础算法（四）
【新手进阶】之五：排序搜索（一）
【新手进阶】之六：排序搜索（二）
【新手进阶】之七：递归算法
【新手进阶】之八：冒泡排序
【新手进阶】之九：浅谈不绑定数据源操作记录
【新手进阶】之十：工作日的计算
【新手进阶】之十一：“庖丁解牛”和“纪昌学射”——浅谈表格式文本数据的导入
【新手进阶】之十二：从四脚腾空的奔马谈起——原来界面可以这样设计
【新手进阶】之十三：Outlook风格导航界面
【新手进阶】之十四：仓库管理系统

ycxchen

第一个学习！

阳春面

学习

JosephTan

有兴趣，看看。

xie62

学习学习学习

风中漫步

那个数列还真没听说过.挺复杂的.其实在生活中类递归的例子真有,如常说的:从前有座山,山上有做庙,庙里有个老和尚在给小和尚讲故事,讲的什么故事呢?从前有座山,山上有做庙,庙里有个老和尚在给小和尚讲故事,......
记得偶上小学时,班里有个同学特有才,那时偶根本不知道这叫有才.他写了篇作文,讲述的是他与父亲搬砖,"搬了一块又一块,搬了一块又一块,搬了一块又一块,.......",直到达到老师要求的字数后才停止了调用.当时这篇作文被老师当众批评了.我学编程后才知道那同学使用的是递归

fnsmydyang

学习了，谢谢。

yanghua1900363

学习！

风中漫步

roych  为什么不是简单的循环语句呢？

递归的特点是自己调用自己.

斑竹讲到这我也就跟进了,这用循环也可解决的.可能我理解的会有偏差,还请斑竹批评指正了.
这个我对低归的理解,请大家批评:

Function by(zs As String) As Long
  If Len(zs) > 100 Then   Exit Function
  Text1 = zs
  zs = zs + "搬了一块又一块,"
  Call by(zs)
End Function

imono

厉害，旁征博引，说的很清楚，谢谢！