1、递归函数递归函数车万翔哈尔滨工业大学两个和尚的故两个和尚的故事事“从前有座山,山里有座庙,庙里有个老和尚给小和 尚讲故事,讲什么呢?”“从前有座山,山里有座 庙,庙里有个老和尚给小和尚讲故事,讲什么呢?”“从前有座山,山里有座庙,庙里有个老和尚给小 和尚讲故事,讲什么呢?”递归的定义递归的定义递归：程序调用自身形式：在函数定义有直接或间接调 用自身阶乘阶乘 阶乘：阶乘：def p(n):x=1i=1while i=n:x=x*i i=i+1return xn=int(raw_input(请输入一个整数:)print n,!的值为,p(n)阶乘阶乘 阶乘：阶乘：p(n)!=()!p(n-1)p(
2、n-1)()!=()!()p(n-2)阶乘阶乘 阶乘：阶乘：else:def p(n):if n=1 or n=0:return 1return n*p(n-1)n=int(raw_input(请输入一个整数:)print n,!的值为：,p(n)阶乘阶乘p(3)def p(3):if 3=1 or 3=0:return 1else:return 3*p(3-1)def p(2):if 2=1 or 2=0:return 1else:return 2*p(2-1)1defifp(1):1=1 or 1=0:return 1else:return 1*p(1-1)26递归初始条件阶乘阶乘def
3、p(n):if n=1 or n=0:return 1else:return n*p(n-1)掐头去尾留中间递归解决问题的思递归解决问题的思想想 if 问题足够简单:直接解决问题返回解 else:将问题分解为与原问题同构的一个或多个更小的问题逐个解决这些更小的问题将结果组合为，获得最终的解返回解兔子数列兔子数列第一个月第二个月 第三个月 第四个月 第五个月 第六个月兔子数列兔子数列 斐波那契数列斐波那契数列是这样一个数列：1,1,2,3,5,8,13,21,34,55,89def fib(n):if n=1 or n=2:return 1初始条件递归else:return fib(n-1)+f
4、ib(n-2)斐波那契数列斐波那契数列 斐波那契数列：斐波那契数列：1,1,2,3,5,8,13,21斐波那契数列斐波那契数列def fib(4):if 4=1 or 4=2:return 1else:return fib(4-1)+fib(4-2)fib(4)def fib(3):if 3=1 or 3=2:return 1else:return fib(3-1)+fib(3-2)def fib(1):if 1=1 or 1=2:return 1else:return fib(1-1)+fib(1-2)def fib(2):if 2=1 or 2=2:return 1else:return
5、fib(2-1)+fib(2-2)递归递归-汉诺塔汉诺塔 在印度，有这么一个古老的传说在印度，有这么一个古老的传说:开天辟地的神勃拉玛（和中国的盘古差不多的神）在一个庙里留下了三 根金刚石的棒，第一根上面套着64个圆的金片，最大的一个在底下，其余 一个比一个小，依次叠上去，庙里的众僧不倦地把它们一个个地从这根棒 搬到另一根棒上，规定可利用中间的一根棒作为帮助，但每次只能搬一个，而且大的不能放在小的上面移动圆片的次数:18446744073709551615递归解决方案递归解决方案将前 n-1 个盘子，通过 C，从 A 移动到 B从 A 到 C 移动第 n 个盘子将前 n-1 个盘子，通过 A，
6、从 B 移动到 C递归递归-汉诺塔汉诺塔定义函数hanoi(n,A,B,C)表示把A上的n个盘子移 动到C上，其中可以用到Bdef hanoi(n,A,B,C):if n=1:print Move disk,n,from,A,to,Celse:hanoi(n-1,A,C,B)print Move disk,n,from,A,to,Chanoi(n-1,B,A,C)n=int(raw_input(请输入一个整数:)hanoi(n,左,中,右)路边停车路边停车随机停车随机停车长度为长度为5的马路，平均能停多少量长度为的马路，平均能停多少量长度为1的汽车？的汽车？随机停车随机停车长度为长度为5的马路
7、，平均能停多少量长度为的马路，平均能停多少量长度为1的汽车？的汽车？随机停车随机停车随机停车随机停车随机停车随机停车随机停车随机停车 当宽度w足够大时，平均停车约 0.7475972w 辆 常数 0.7475972 被称作 Renyi 停车常数 该算法巧妙的运用了递归思想，将大问题分解为更小的、独 立的相似问题，然后分别加以解决 许多问题能够以此方式解决递归的时间开递归的时间开销销def fib_loop(n):if n=1 or n=2:return 1else:i=2f1=1f2=1while(i n):f3=f1+f2 f1=f2f2=f3i=i+1 return f3def fib_r
8、ecursive(n):if n=1 or n=2:return 1else:return fib_recursive(n-1)+fib_recursive(n-2)fib_loop(100)fib_recursive(100)不到0.01秒超过1小时时间都去哪了？递归的时间开递归的时间开销销def fib(4):if 4=1 or 4=2:return 1else:return fib(4-1)+fib(4-2)fib(4)def fib(3):if 3=1 or 3=2:return 1else:return fib(3-1)+fib(3-2)def fib(1):if 1=1 or 1=2:return 1else:return fib(1-1)+fib(1-2)def fib(2):if 2=1 or 2=2:return 1else:return fib(2-1)+fib(2-2)递归的优劣分递归的优劣分析析优势优势（strength）它能使一个蕴含递归关系且结构复杂的程序简洁精炼，增加可读性特别是在难于找到从边界到解的全过程的情况下，如果 把问题推进一步,其结果仍维持原问题的关系劣势劣势（weakness）嵌套层次深，函数调用开销大重复计算
