c语言递归算法PPT课件.pptx

第八章 递归算法
1
3
2
基本概念
基于回溯策略的递归
基于分治策略的递归
第1页/共117页
从前有座山，山上有座庙，庙里有一个老和尚
和一个小和尚，老和尚正在给小和尚讲故事。
讲的是什么故事呢？他说，从前……
第2页/共117页
Recursion
- See "Recursion".
"In order to understand recursion, one must first understand recursion."
第3页/共117页
C语言允许嵌套地调用函数，也就是说，在调用
一个函数的过程中，又去调用另一个函数。
函数的嵌套调用
void main( )
{
…
study_english ( );
…
}
void study_english( )
{
reading( );
listening( );
writing( )
}
void listening( )
{
…
…
…
}
第4页/共117页
函数的嵌套调用有一个特例，即递归调用，也就
是说，在调用一个函数的过程中，又出现了直接
或间接地去调用该函数本身。
void tell_story( )
{
int old_monk, young_monk;
tell_story ( ); // tell_story 函数的递归调用
}
函数的递归调用
?
第5页/共117页
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("对不起，已退休！"); // 递归边界
}
第6页/共117页
在语法上（简单）
递归即为普通的函数调用。
在算法上（难）
如何找到递归形式？
如何找到递归边界？
如何编写递归程序？
第7页/共117页
递归算法的类型
递归算法可以分为两种类型：
基于分治策略的递归算法；
基于回溯策略的递归算法。
第8页/共117页
第八章 递归算法
1
3
2
基本概念
基于回溯策略的递归
基于分治策略的递归
第9页/共117页
分而治之（divide-and-conquer）的算法
设计思想：
Divide：把问题划分为若干个子问题；
Conquer：以同样的方式分别去处理各个子问题；
Combine：把各个子问题的处理结果综合起来，形成最终的处理结果。
分而治之
第10页/共117页