搜索
递归函数车万翔哈尔滨工业大学两个和尚的故事“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”“从前有座山,山里有座庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”………………………递归的定义递归：程序调用自身形式：在函数定义有直接或间接调用自身阶乘阶乘：defp(n):x=1i=1whilei=n:x=x*ii=i+1returnxn=int(raw_input(请输入一个整数:))printn,!的值为,p(n)阶乘阶乘：p(n)�!=(�−�)!×�p(n-1)p(n-1)(�−�)!=(�−�)!×(�−�)p(n-2)阶乘阶乘：else:defp(n):ifn==1orn==0:return1returnn*p(n-1)n=int(raw_input(请输入一个整数:))printn,!的值为：,p(n)阶乘p(3)defp(3):if3==1or3==0:return1else:return3*p(3-1)defp(2):if2==1or2==0:return1else:return2*p(2-1)1defifp(1):1==1or1==0:return1else:return1*p(1-1)26递归初始条件阶乘defp(n):ifn==1orn==0:return1else:returnn*p(n-1)掐头去尾留中间递归解决问题的思想if问题足够简单:直接解决问题返回解else:将问题分解为与原问题同构的一个或多个更小的问题逐个解决这些更小的问题将结果组合为，获得最终的解返回解兔子数列第一个月第二个月第三个月第四个月第五个月第六个月兔子数列斐波那契数列是这样一个数列：1,1,2,3,5,8,13,21,34,55,89……deffib(n):ifn==1orn==2:return1初始条件递归else:returnfib(n-1)+fib(n-2)斐波那契数列斐波那契数列：1,1,2,3,5,8,13,21……斐波那契数列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递归解决方案将前n-1个盘子，通过C，从A移动到B从A到C移动第n个盘子将前n-1个盘子，通过A，从B移动到C递归-汉诺塔定义函数hanoi(n,A,B,C)表示把A上的n个盘子移动到C上，其中可以用到Bdefhanoi(n,A,B,C):ifn==1:printMovedisk,n,from,A,to,Celse:hanoi(n-1,A,C,B)printMovedisk,n,from,A,to,Chanoi(n-1,B,A,C)n=int(raw_input(请输入一个整数:))hanoi(n,'左','中','右')路边停车随机停车长度为5的马路，平均能停多少量长度为1的汽车？随机停车长度为5的马路，平均能停多少量长度为1的汽车？随机停车随机停车随机停车随机停车当宽度w足够大时，平均停车约0.7475972w辆常数0.7475972被称作Renyi停车常数该算法巧妙的运用了递归思想，将大问题分解为更小的、独立的相似问题，然后分别加以解决许多问题能够以此方式解决递归的时间开销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)递归的优劣分析优势（strength）它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性特别是在难于找到从边界到解的全过程的情况下，如果把问题推进一步,其结果仍维持原问题的关系劣势（weakness）嵌套层次深，函数调用开销大重复计算