数据结构课件 第十一章 递归.ppt

文档介绍：第十一章递归
递归的定义
常见递归问题
递归的实现
递归转化为非递归的一般过程
递归的时间和空间复杂度
递归的定义
概念:
递归:一个事件或对象部分的由自己组成,或者按它自己来定义
递归算法分为递推和回归
递推: 为得到问题的解,将其推到比原来问题简单的问题求解上
回归:简单问题得到解后,回归到原问题的解上
递归函数分类:
直接递归:函数直接调用本身
A( )
{……
CALL A( )
......
}
间接递归:一函数在调用其他函数时,又产生了对自身的调用
A( ) B( )
{……{……
CALL B() CALL A()
……} ……}
常见递归问题
汉诺塔问题
八皇后问题
组合公式的计算
. 汉诺塔问题
问题描述:有三个命名为A、B、C的塔座,在塔座A上插有n个直径各不相同的,从小到大依次编号为1,2,3,……,n的圆盘,编号越大的圆盘其直径越大;要求将A轴上的n个圆盘全部移至塔座C上并仍按同样顺序叠放,并且圆盘移动时必须遵循下列规则:
每次只能移动一个圆盘;
圆盘可以插入A、B、C中任一个塔座上;
任何时候都不能将一个较大的圆盘压在较小的圆盘上
事例:n=3
事例:n=6
算法:
void hanoi ( int n, char x, char y, char z)
{/*递归算法*/
if(n= =1) move(x,z);
else
{
hanoi(n-1,x,z,y);/*把N-1个盘子从X借助Z移到Y*/
printf(”%c-%c\n”, x,z);/*把盘子N从X直接移到Z*/
hanoi(n-1,y,x,z);/*把N-1个盘子从Y借助X移到Z */
}
}
. 八皇后问题
问题描述:在一个88的棋盘上放置8个皇后,那么n个皇后的问题就是在nn的棋盘上放置n个皇后;规则是:不允许两个皇后在同一行,同一列或同一对角线上
图示:
事例:四皇后问题: