递归算法实例及程序实现

递归算法实例及程序实现从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？老和尚的故事…数果子问题233142？数果子问题递归

将要处理的问题划分为一个或多个子问题，而处理子问题的方法与处理原问题的方法是一样的，这样的处理方法称为递归。案例一、到底几岁了？我比左边的2倍小2岁我比左边的2倍小2岁我比左边的2倍小2岁我比左边的2倍小2岁我比左边的2倍小2岁我比左边的2倍小2岁我3岁案例一、到底几岁了？算法规则：1、第1个人的年龄=3\2、第N个人的年龄=第N-1人的年龄*2-2求第N个人的年龄：if是第1个人then年龄=3 else年龄=前一人年龄*2-2 endif案例一、到底几岁了？VB代码：FunctionAge(nAsInteger)AsIntegerifn=1thenage=3elseage=age(n-1)*2-2endifEndFunction求第N个人的年龄if是第一个人then

年龄=3else

年龄=前一人年龄*2-2endif案例二、斐波那契数列问题斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、34、65……这个数列从第三项开始，每一项都等于前两项之和。求：数列中的第N项是几？算法规则：1、最初两项值为12、第N项的值是它之前两项之和求第N个斐波纳切数if是最初两项then斐波纳切数=1 else斐波纳切数=前两个斐波纳切数之endif案例二、斐波那契数列问题求第N个斐波纳切数if是最初两项then斐波纳切数=1 else斐波纳切数=前两个斐波纳切数之和endifFunctionFib(nasInteger)asIntegerIfthenFib=ElseFib=EndifEndFunctionn<3Fib(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)asIntegerIfn<3thenFib=1ElseFib=Fib(n-2)+Fib(n-1)EndifEndFunction从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？从前有座山，山里有座庙，庙里有个老和尚，给小和尚讲故事，故事是什么呢？再看老和尚的故事…这个过程算不算是递归？怎么改才能算是递归？拓展练习:求n!n!=1×2×3×4×……×nn!=(n-1)!×n1!=1拓展练习:恶魔与农夫有一位农夫不满于自己的贫困。一天,他正在抱怨上天的不公平,一个恶魔出现在他的眼前，他对农夫说:“