c语言 递归算法.ppt

计算机语言与程序设计
谌卫军
清华大学软件学院
Introduction puter Programming
第八章递归算法
1
3
2
基本概念
基于回溯策略的递归
基于分治策略的递归
从前有座山,山上有座庙,庙里有一个老和尚
和一个小和尚,老和尚正在给小和尚讲故事。
讲的是什么故事呢?他说,从前……
Recursion
- See "Recursion".
"In order to understand recursion, one must first understand recursion."
C语言允许嵌套地调用函数,也就是说,在调用
一个函数的过程中,又去调用另一个函数。
函数的嵌套调用
void main( )
{
…
study_english ( );
…
}
void study_english( )
{
reading( );
listening( );
writing( )
}
void listening( )
{
…
…
…
}
函数的嵌套调用有一个特例,即递归调用,也就
是说,在调用一个函数的过程中,又出现了直接
或间接地去调用该函数本身。
void tell_story( )
{
int old_monk, young_monk;
tell_story ( ); // tell_story 函数的递归调用
}
函数的递归调用
?
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("对不起,已退休!"); // 递归边界
}
在语法上(简单)
递归即为普通的函数调用。
在算法上(难)
如何找到递归形式?
如何找到递归边界?
如何编写递归程序?
递归算法的类型
递归算法可以分为两种类型:
基于分治策略的递归算法;
基于回溯策略的递归算法。