python基础教程-递归函数

递归函数哈尔滨工业大学计算机学院叶麟函数体函数头复习–函数f(x)=x2–2x+1deff(x):y=x**2–2*x+1returny关键字函数名参数缩进函数：是完成特定功能的一个语句组，通过函数名执行输入：参数输出：返回值递归–两个和尚“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”………………………………………….自己调用自己递归–德罗斯特效应递归–定义递归：程序调用自身形式：在函数定义有直接或间接调用自身递归-阶乘defp(n):x=1i=1while(i=n):x=x*ii=i+1returnxn=input(请输入一个整数:)printn,!的值为,p(n)递归-阶乘p(n)p(n-1)p(n-1)p(n-2)()递归-阶乘defp(n):returnn*p(n-1)ifn==1orn==0:return1else:n=input(请输入一个整数:)printn,!的值为：,p(n)递归-阶乘p(3)defp(3):if3==1or3==0:return1;else:return3*p(3-1)defp(2):if2==1or2==0:return1;else:return2*p(2-1)defp(1):if1==1or1==0:return1;else:return1*p(1-1)递归条件递归出口递归-阶乘defp(n):ifn==1orn==0:return1else:returnn*p(n-1)n=input(请输入一个整数:)printn,!的值为：,p(n)掐头去尾留中间递归–兔子数列第一个月第二个月第三个月第四个月第五个月第六个月递归–兔子数列斐波那契数列是这样一个数列：1,1,2,3,5,8,13,21,34,55,89……斐波那契数列：1,1,2,3,5,8,13,21……递归-斐波那契数列deffib(n):ifn==1orn==2:return1else:i=2f1=1f2=1while(in):f3=f1+f2f1=f2f2=f3i=i+1returnf3递归条件递归出口递归-斐波那契数列斐波那契数列：1,1,2,3,5,8,13,21……deffib(n):returnfib(n-1)+fib(n-2)ifn==1orn==2:return1else:n=input(请输入一个整数:)printfib(n)递归-斐波那契数列deffib(4):if4==1or4==2:return1else:returnfib(4-1)+fib(4-2)fib(4)deffib(3):if3==1or3==2:return1else:returnfib(3-1)+fib(3-2)deffib(1):if1==1or1==2:return1else:returnfib(1-1)+fib(1-2)deffib(2):if2==1or2==2:return1else:returnfib(2-1)+fib(2-2)递归-汉诺塔在印度，有这么一个古老的传说:开天辟地的神勃拉玛（和中国的盘古差不多的神）在一个庙里留下了三根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面移动圆片的次数:18446744073709551615递归-汉诺塔定义函数hannoi(n,A,B,C)表示把A上的n个盘子移动到C上，其中可以用到Bdefhannoi(n,A,B,C):hannoi(n-1,A,C,B)printMovedisk,n,from,A,to,Channoi(n-1,B,A,C)ifn==1:printMovedisk,n,from,A,to,Celse:n=input(请输入一个整数:)hannoi(n,'左','中','右')递归deffib_loop(n):ifn==1orn==2:return1else:i=2f1=1f2=1while(in):f3=f1+f2f1=f2f2=f3i=i+1returnf3deffib_recursive(n):ifn==1orn==2:return1else:returnfib_recursive(n-1)+fib_recursive(n-2)fib_loop(100)fib_recursive(100)不到0.01秒超过1小时时间都去哪了递归deffib(4):if4==1or4==2:return1else:returnfib(4-1)+fib(4-2)fib(4)deffib(3):if3==1or3==2:return1else:returnfib(3-1)+fib(3-2)deffib(1):if1==1or1==2:return1else:returnfib(1-1)+fib(1-2)deffib(2):if2==1or2==2:return1else:returnfib(2-1)+fib(2-2)递归–SW分析优势（strength）它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性特别是在难于找到从边界到解的全过程的情况下，如果把问题推进一步,其结果仍维持原问题的关系劣势（weakness）嵌套层次深，函数调用开销大重复计算本章小结递归自己调用自己递归要素递归出口：也就是所描述问题的最简单情况，它本身不再使用递归的定义。递归关系：使问题向递归出口转化的规则。递归定义必须能使问题的规模越来越简单有选择地使用递归递归–盗梦空间元芳，你怎么看