递归算法-精.ppt

天津城市建设学院
电子与信息工程系
计算机应用教研室
算法设计与分析
唐国峰
******@tjuci.
Lesson 2 递归算法
天津城市建设学院
2011年3月3日
什么是递归?
当你往镜子前面一站,镜子里面就有一个你的像。但你试过两面镜子一起照吗?如果甲、乙两面镜子相互面对面放着,你往中间一站,嘿,两面镜子里都有你的千百个“化身”!为什么会有这么奇妙的现象呢?原来,甲镜子里有乙镜子的像,乙镜子里也有甲镜子的像,而且这样反反复复,就会产生一连串的“像中像”。这是一种递归现象。
Lesson 2 递归算法
天津城市建设学院
2011年3月3日
什么是递归?
这种日常生活中的现象又被称为德罗斯特效应(英语:Droste effect)是递归的一种视觉形式。
图中女性手持的物体中有一幅她本人手持同一物体的小图片,进而小图片中还有更小的一幅她手持同一物体的图片,依此类推。
Lesson 2 递归算法
天津城市建设学院
2011年3月3日
什么是递归?
在日常生活中,递归一词较常用于描述以自相似方法重复事物的过程。
在算法中,递归一词用于表示直接或间接的调用自身的算法。
特别的,用函数自身给出定义的函数被称之为递归函数。
Lesson 2 递归算法
天津城市建设学院
2011年3月3日
什么是递归?
其实,我们在生活中经常运用递归的方式来思考问题,如参考下面这个例子:
例1:第5个人的年龄比第4个人的年龄大2岁,第4个人的年龄比第3个人的年龄大2岁,第3个人的年龄比第2个人的年龄大2岁,第2个人的年龄比第1个人的年龄大2岁,第1个的年龄10岁。第5个人的年该该是多少呢?
Lesson 2 递归算法
天津城市建设学院
2011年3月3日
著名的意大利数学家斐波那契(i)在他的著作《算盘书》中提出了一个“兔子问题”:假定小兔子一个月就可以长成大兔子,而大兔子每个月都会生出一对小兔子。如果年初养了一对小兔子,问到年底时将有多少对兔子?  (当然得假设兔子没有死亡而且严格按照上述规律长大与繁殖)
Lesson 2 递归算法
天津城市建设学院
2011年3月3日
①输入计算兔子的月份数:n
② If n < 3 Then c = 1 Else a = 1;b = 1
③ i = 3
④ c = a + b
a = b
b = c
⑤ i=i+1,如果i≤n则返回④
⑥结束
Lesson 2 递归算法
天津城市建设学院
2011年3月3日
1月
2月
3月
4月
5月
6月
7月
8月
9月
10月
11月
12月
小兔
1
1
1
2
3
5
8
13
21
34
55
大兔
1
1
2
3
5
8
13
21
34
55
89
合计
1
1
2
3
5
8
13
21
34
55
89
144
这个表格虽然解决了斐波那契的兔子问题(年底时兔子的总数是144对),但仔细观察一下这个表格,你会发现兔子的数目增长得越来越快,如果时间再长,只用列表的方法就会有困难。(例如,你愿意用列表的方法求出5年后兔子的数目吗?)我们需要研究表中的规律,找出一般的方法,去解决这个问题。
Lesson 2 递归算法
天津城市建设学院
2011年3月3日
仔细研究上页的表,你有些什么发现?每一个月份的大兔数、小兔数与上一个月的数字有什么联系,能肯定这个规律吗?恭喜你,你快成功了?
Lesson 2 递归算法
天津城市建设学院
2011年3月3日
“兔子问题”很容易列出一条递推式而得到解决。假设第N个月的兔子数目是F(N),我们有:
这是因为每月的大兔子数目一定等于上月的兔子总数,而每个月的小兔子数目一定等于上月的大兔子数目(即前一个月的兔子的数目)。