递归算法实例.doc

《递归算法实例.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、递归算法实例忘记关窗子给冷风吹醒了，额！前段时间研究PHP，关于递归有个例题“馋嘴猴子”。说有只猴子弄到了一堆桃子，它第一天吃了这堆的一半，还觉得不过瘾，出门的时候又吃了一个，第二天吃了剩下的桃子的一半再加一个，每天都这样，第十天准备吃的时候，发现桃子只剩一个了，问最初一共有多少个桃子。问题并不复杂，但是要用倒着推的方式，第十天的桃子数量1也就是第九天剩下的数量，设第九天桃子数量为X,则有等式：X/2-1=1，解得:X=4。以此类推可以算出最初的桃子数量。用编程的方式解决这个问题，有两种推导方式，“迭代”和“递归”。今天主要说说编程中递归，递归说白了就是函数自己调

2、用自己，这种流程控制方法和“迭代”一样，都是用在代码执行步进中，后一步的计算结果当做前一步计算参数的时候。“递归”的关键是出口，就是结束递归的条件，条件设置不合适，容易死循环。来个简单的例子----阶乘，阶乘就是自然数从1乘到自己本身，比如3的阶乘，就是1x2x3=6。用VBA实现，按正常的流程做法应该是：FunctionFactorial0(ByValnumAsInteger)DimiAsLongFactorial0=1Fori=1TonumFactorial0=Factorial0*iNextiEndFunction这么写也无可厚非，比较容易理解，用递归写阶乘

3、代码是下面这样的：FunctionFactorial(ByValnumAsInteger)Ifnum=1Then'这里设置的是递归的出口，NUM是1就结束Factorial=1ElseFactorial=num*Factorial(num-1)'这里是重点，自己调用自己，变量NUM减1EndIfEndFunction接着上面“馋嘴猴子”的问题，用递归解决代码如下：Functionpeach2(ByValkAsInteger)Dimii=1Ifi=kThen'设置递归出口，当天数等于K则结束peach2=1Elsepeach2=2*(peach2(i+1)+1)'递

4、归调用自身的部分i=i+1EndIfEndFunction下面是“迭代”的代码，我也放上来，对比一下：Functionpeach(ByValkAsInteger)DimiAsInteger,resAsLongres=1Fori=k-1To1Step-1res=2*(res+1)peach=res*2NextiEndFunction