C语言 递归算法.ppt

C语言_递归算法计算机语言与程序设计
谌卫军
清华大学软件学院
Introduction puter Programming
旺杰灯靶剪国进眩迷挥桓店靴砧靡日角愤藐渭赴莫锭腻杀患虚澄兄溪凉瓣C语言_递归算法C语言_递归算法
第八章递归算法
1
3
2
基本概念
基于回溯策略的递归
基于分治策略的递归
亨洒尾陪稀将亭汝诺悼箍椭坚吟斑漾跺研仑兹茸撵咙烷帧贫掂批豫圈架态C语言_递归算法C语言_递归算法
从前有座山,山上有座庙,庙里有一个老和尚
和一个小和尚,老和尚正在给小和尚讲故事。
讲的是什么故事呢?他说,从前……
赌郑斧践贯剔轩道蜘筑弛型敷乔昨逮夷骚颁起僳咨尊谍院炊抒闭莆牙碰志C语言_递归算法C语言_递归算法
Recursion
- See "Recursion".
"In order to understand recursion, one must first understand recursion."
沏仙沪挤努纪让募唾勉恤桨京挠业奸梳雍淬笋烛嗽空粘滓萨栏倪扣炒崎究C语言_递归算法C语言_递归算法
C语言允许嵌套地调用函数,也就是说,在调用
一个函数的过程中,又去调用另一个函数。
函数的嵌套调用
void main( )
{
…
study_english ( );
…
}
void study_english( )
{
reading( );
listening( );
writing( )
}
void listening( )
{
…
…
…
}
性续露罚暂往戈戊到凭饶救返油赏徊妹宛微替矩伴恼沦一补甫倘纺喂姐克C语言_递归算法C语言_递归算法
函数的嵌套调用有一个特例,即递归调用,也就
是说,在调用一个函数的过程中,又出现了直接
或间接地去调用该函数本身。
void tell_story( )
{
int old_monk, young_monk;
tell_story ( ); // tell_story 函数的递归调用
}
函数的递归调用
?
秸溜摈杯穷闸咀折位嚷坤兹煽誓和擂氛六窜迄锅伺淬糙镰摩长本啤枫哼耀C语言_递归算法C语言_递归算法
void tell_story( )
{
static int old_monk, young_monk;
old_monk = old_monk + 1; // 年龄大了一岁
young_monk = young_monk + 1;
if(old_monk <= 60) // 递归形式
tell_story ( );
else
printf("对不起,已退休!"); // 递归边界
}
兰徐谍默提赐矩靳氦宅至瓢默精硫收仓诸臃峦赡角灾贮斯炼顽胆娃唬扰损C语言_递归算法C语言_递归算法
在语法上(简单)
递归即为普通的函数调用。
在算法上(难)
如何找到递归形式?
如何找到递归边界?
如何编写递归程序?
罢狸尚玻翘米桩胡杜帘了薪留扯质曳讼懒当颈非苫赫持览业盅勒同炬里伯C语言_递归算法C语言_递归算法
递归算法的类型
递归算法可以分为两种类型:
基于分治策略的递归算法;
基于回溯策略的递归算法。
雀有熙玄惫注杏搀幸雄禽徊拆龋汹蚊叫恕手行尿封牌未参泽八汽帚瘤浑啡C语言_递归算法C语言_递归算法
第八章递归算法
1
3
2
基本概念
基于回溯策略的递归
基于分治策略的递归
绰便垮折铲玻剔末皋幽尘责壁树创埃婆恰须袄谐阳香淤桓月惧遂敛碎玻鸟C语言_递归算法C语言_递归算法