算法设计与分析：第2章 算法分析基础-2(递归).pptx

2015年9月16日星期三
学习要点:
递归算法的实现机制。
递归算法的设计。
如何消去递归。
如何计算递归关系式。
典型递归算法和计算式的求解。
递 归
2015年9月16日星期三
递归算法的实现机制
一个直接或
1. 编写一个计算 n! 的程序.
int f( int n）
{ int r；
if (n<=1) r=1;
else r=n*f(n-1);
return r ;
}
n！=1·2·3·……·（n-1）·n， n≥1 非递归形式的定义
1 若n≤0
f(n) = 递归定义
n · f(n-1) 若n>0
分析: n! = n * (n - 1) * (n - 2) * ... * 1 = n * (n - 1)! (n - 1)! = (n - 1) * (n - 2)! …... 2! = 2 * 1! 1! = 1
递归函数上层与下层之间的关系
递归的出口
2015年9月16日星期三
定义
F(n)=
1, n=1
1, n=2
F(n-1)+F(n-2), n>2
非递归部分,边界(终止)条件
递归部分,起始条件
Procedure F(n)
integer n
if n≤2 then return(1) ————递归出口
else return(F(n-1)+F(n-2))——递归
end if
End F
2 Fibonacci数列
2015年9月16日星期三
2015年9月16日星期三
在编写递归函数时要注意，函数中的局部变量和参数，局限于当前调用层，当递推进入“简单问题操作”层时，原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题操作”层，它们各有自己的参数和局部变量。    
例如上面计算斐波那契数列的第n项的函数F(n)应采用递推算法，即从斐波那契数列的前两项出发，逐次由前两项计算出下一项，直至计算出要求的第n项。
procedure P(参数表)；
if 递归出口
then 简单操作1
else
简单操作2；call P；简单操作3
endif
EndP;
2015年9月16日星期三
3 Hanoi塔问题
当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座A直接移至塔座C上即可。（AC)
当n＞1时，需要利用塔座B作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座A移至塔座B，然后，将剩下的最大圆盘从塔座A移至塔座C，最后，再设法将n-1个较小的圆盘依照移动规则从塔座B移至塔座C。
（AB, AC, BC)
由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法。
2015年9月16日星期三
void hanoi( int n, int A, int B, int C)
{
if (n > 0)
{
hanoi(n-1, A, C, B);
move( A , C);
hanoi(n-1, B, A, C);
}
}
void Hanoi(int n,char A,char B,char C)
{
if (n==1）
printf (A—>C);
else
{
hanoi(n-1,A,C,B);
printf(A—>C);
hanoi(n-1,B,A,C);
}
}
2015年9月16日星期三
4 求n个元素的全排列。
分析：n=1 输出a1;
n=2 输出a1 a2;
a2 a1;
n=3 输出a1 a2 a3;
a1 a3 a2;