搜索
递归算法从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？老和尚的故事…案例一、小猴吃桃•有一天小猴子摘若干个桃子,当即吃了一半还觉得不过瘾,又多吃了一个。第二天接着吃剩下桃子中的一半，仍觉得不过瘾又多吃了一个，以后小猴子都是吃尚存桃子一半多一个。到第10天早上小猴子再去吃桃子的时候，看到只剩下一个桃子。问小猴子第一天共摘下了多少个桃子?我们能不能这样设一个函数：•算法描述：•function你有多少桃子？（第几天）•如果第10天，那么•桃子数=1•否则••endfunction桃子数=第n天的桃子数第n+1天的桃子数2-1=第n天的桃子数=(第n+1天的桃子数+1)*2（明天的桃数+1）*2•算法实现：•Functiontao(daysAsInteger)AsInteger•Ifdays=10Then•tao=1•Else•tao=(tao(days+1)+1)*2•EndIf•EndFunctionTao(1)=(tao(2)+1)*2Tao(2)=(tao(3)+1)*2Tao(3)=(tao(4)+1)*2Tao(8)=(tao(9)+1)*2Tao(9)=(tao(10)+1)*2Tao(10)=1调用调用调用调用调用返回返回返回返回返回案例二、斐波那契数列问题斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、34、55……这个数列从第三项开始，每一项都等于前两项之和。求：数列中的第N项是几？算法规则：1、最初两项值为12、第N项的值是它之前两项之和求第N个斐波纳切数if是最初两项then斐波纳切数=1else斐波纳切数=前两个斐波纳切数之和endif案例二、斐波那契数列问题求第N个斐波纳切数if是最初两项then斐波纳切数=1else斐波纳切数=前两个斐波纳切数之和endifFunctionFib(nasInteger)asIntegerIfthenFib=ElseFib=EndifEndFunctionn3Fib(n-2)+Fib(n-1)11、1、2、3、5、8、13、21、34、65……案例三、求最大公约数早在公元前300年左右，欧几里得就在他的著作《几何原本》中给出了高效的解法——辗转相除法。辗转相除法的方法是用较大的数X除以较小的数Y，得到余数Z如果余数为0，则较小数Y就是两者的最大公约数。例如：27和9的最大公约数就是9如果余数不为0，则较小数Y与余数Z的最大公约数就是X与Y的的最大公约数例如：33和9的最大公约数就是9与6的最大公约数案例三、求最大公约数求X与Y的公约数：Z是X除Y得到的余数IfZ为0then公约数=Else公约数=的公约数EndifFunctionGYS(xasInteger,yasInteger)asIntegerDimzasIntegerz=IfZ=0thenGYS=ElseGYS=EndifEndFunctionXmodYYGYS(Y,Z)Y和ZY递归将要处理的问题划分为一个或多个子问题，而处理子问题的方法与处理原问题的方法是一样的，这样的处理方法称为递归递归算法小结•在程序中，递归算法表现为函数在运行过程中调用了自己。•每一次递归调用，在处理问题的规模上都有所缩小•在问题的规模极小时，必须能给出直接的解答求年龄：FunctionAge(nAsInteger)AsIntegerifn=1thenage=3elseage=age(n-1)*2-2endifEndFunction求斐波那契数：FunctionFib(nasInteger)asIntegerIfn3thenFib=1ElseFib=Fib(n-2)+Fib(n-1)EndifEndFunction从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？再看老和尚的故事…这个过程算不算是递归？怎么改才能算是递归？拓展练习:求n!•n!=1×2×3×4×……×n•n!=(n-1)!×n•1!=1拓展练习:恶魔与农夫•有一位农夫不满于自己的贫困,一天,他正在抱怨上天的不公平,一个恶魔出现在他的眼前.他对农夫说:“我可以帮助你,你只要从桥上每走一次,你口袋里的钱就会增加一倍.但是作为报酬,每次你要付给我24法郎,如何?”农夫看了看自己口袋里的钱,不假思索地答应了。但是三次之后，农夫身上连一毛钱都没剩下。那么这个农民在遇见魔鬼以前有多少钱呢？