算法分析与设计
主讲教师 刘寒冰
第2章 递归与分治算法
第一讲 递 归
练习题
1、函数T(n)=5n
100
+1000n
2
+2
n
用O可表示为（）
A.O(n
2
)B.O(1)C.O(2
n
)D.O(n
100
)
2、函数T(n)=3n
3
+2
100
n+10
100
用θ可表示为（）
A.θ(n
100
)B.θ(1)C.θ(n)D.θ(n
3
)
3、函数T(n)=2n
2
+100n+1用Ω可表示为（）
A.Ω(nlogn)B.Ω(1)C.Ω(n
2
)D.Ω(n
3
)
4、函数T(n)=10
100
用O可表示为（）
A.O(nlogn)B.O(1)C.O(n)D.O(n
3
)
5、函数T(n)=2n
3
+100n+10
100
用Ω可表示为（）
A.Ω(nlogn)B.Ω(1)C.Ω(n
5
)D.Ω(n
3
)
· 理解递归的定义及执行过程；
· 掌握递归的典型应用；
· 理解使用递归的条件及递归的优缺点。
· 本节重点：递归的定义、执行过程及典型应用
· 本节难点：递归的执行过程
学习要求
定义子函数
int f1( int x1 )
{
…
return z1;}
int f2( int x2 )
{…
a=f1( y1 );
…
return z2;}
int f3( int x3 )
{…
b=f2( y2 );
…
return z3;}
int f4(int x4 )
{…
c=f3( y3);
…
return z4;}
Main()
{
int d,y;
scanf(“%d”,&y);
d=f4( y );
Printf(“%d”,d);
}
当函数中出现调用子函数时，系统将自动把函数中当
前的变量、形参和调用结束后的返回地址暂时保留起
来，在新一轮的调用过程中，系统为新调用的函数所
用到的变量和形参开辟另外的存储单元（内存空间
）。每次调用函数所使用的变量在不同的内存空间。
当本次调用的函数运行结束时，系统将释放本次调用
时所占用的内存空间。程序的流程返回到上一层的调
用点，同时取得当初进入该层时，函数中的变量和形
参所占用的内存空间的数据。
