文档介绍：栈的应用举例—递归
1 递归的定义
子程序（或函数）直接调用自己或通过一系列调用语句间接调用自己，是一种描述问题和解决问题的基本方法。
2 递归的基本思想
问题分解：把一个不能或不好解决的大问题转化为一个或几个小问题，再把这些小问题进一步分解成更小的小问题，直至每个小问题都可以直接解决。
2021/1/15
1
递归程序的设计
3 递归的要素
⑴ 递归边界条件：确定递归到何时终止，也称为递归出口；
⑵ 递归模式：大问题是如何分解为小问题的，也称为递归体。
栈的应用举例—递归
2021/1/15
2
递归程序的设计
例1 阶乘函数
递归算法
int fact ( int n )
{
if ( n == 0 ) return 1;
else return n * fact (n-1);
}
-
*
=
时
当
时
当
)!
1
(
1
!
n≥1
n＝1
n
n
n
栈的应用举例—递归
2021/1/15
3
递归程序的设计
求解阶乘 n! 的过程
计算 fact(4)
计算 4*fact(3)
计算 3*fact(2)
计算 2*fact(1)
计算 fact(1)
递归调用
回归求值
返回 24
返回 6
返回 2
返回1
栈的应用举例—递归
2021/1/15
4
递归程序的设计
递归过程与递归工作栈
递归过程在实现时，需要自己调用自己。
层层向下递归，返回次序正好相反：
递归调用
n! (n-1)! (n-2)! 1!=1
返回次序
栈的应用举例—递归
2021/1/15
5
递归程序的设计
递归的经典问题——汉诺塔问题
在世界刚被创建的时候有一座钻石宝塔（塔A），其上有64个金碟。所有碟子按从大到小的次序从塔底堆放至塔顶。紧挨着这座塔有另外两个钻石宝塔（塔B和塔C）。从世界创始之日起，婆罗门的牧师们就一直在试图把塔A上的碟子移动到塔C上去，其间借助于塔B的帮助。每次只能移动一个碟子，任何时候都不能把一个碟子放在比它小的碟子上面。当牧师们完成任务时，世界末日也就到了。
栈的应用举例—递归
2021/1/15
6
递归程序的设计
汉诺塔问题的递归求解:
如果 n = 1，则将这一个盘子直接从 塔A移到塔 C 上。否则，执行以下三步：
⑴ 将塔A上的n-1个碟子借助塔C先移到塔B上；
⑵ 把塔A上剩下的一个碟子移到塔C上；
⑶ 将n-1个碟子从塔B借助于塔A移到塔C上。
栈的应用举例—递归
2021/1/15
7
递归程序的设计
2021/1/15
8
递归程序的设计
void Hanoi(int n, char A, char B, char C)
{  
if (n==1) Move(A, C);
     else {              
Hanoi(n-1, A, C, B);
     Move(A, C);
          Hanoi(n-1, B, A, C);              
}       
}
栈的应用举例—递归
2021/1/15
9
递归程序的设计
递归函数的内部执行过程
每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。
每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。
局部变量
返回地址
值 参
活动记录框架
递归
工作记录
⑴ 运行开始时，首先为递归调用建立一个工作栈，其结构包括值参、局部变量和返回地址；
⑵ 每次执行递归调用之前，把递归函数的值参和局部变量的当前值以及调用后的返回地址压栈；
⑶ 每次递归调用结束后，将栈顶元素出栈，使相应的值参和局部变量恢复为调用前的值，然后转向返回地址指定的位置继续执行。
栈的应用举例—递归
2021/1/15
10
递归程序的设计