栈与递归的实现
递归函数：一个直接调用自己或通过一些列的调用语句间接地调用自己的函数
递归是程序设计中一个强有力的工具，有下面三种类型：
- 递归定义的数学函数；
- 有的数据结构，如二叉树、广义表等，由于结构本身故有的递归特性，则他们的操作可以递归地描述；
- 虽然问题本身没有明显的递归结构，但用递归求解比迭代求解更简单，如八皇后问题、Hanoi塔问题。
n阶Hanoi塔问题
问题描述
假设有3个分别命名为X、Y和Z的塔座，在塔座X上插有n个直径大小各不相同、依小到大表号为1,2,…,n的圆盘。
现要求将X上的n个圆盘移至塔座Z上并仍按同样顺序排叠，圆盘移动时必须遵循以下规则：
- 每次只能移动一个圆盘；
- 圆盘可以叉在X、Y和Z中的任一塔座上；
- 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
实现方法
n = 1时，只要将编号为1的圆盘从塔座X直接移至塔座Z上即可；
n > 1时，续利用塔座Y作辅助塔，将压在编号n的圆盘上的n-1个圆盘从塔座X移动到塔座Y上，则可将编号为n的圆盘从塔座X移至塔座Z上，然后再将塔座Y上的n-1个圆盘移动到塔座Z上(依照前法)；
void hanoi(int n, char x, char y, char z) {
// 将塔座x上按直径由大到小且自上而下编号为1至n的n个圆盘按规
// 搬到塔座z上，y可用作辅助塔座。
// move(x, n, z)：将编号为n的圆盘从x移动到z
if(n == 1) move(x, 1, z); // 将编号为1的圆盘从x移动到z
else {
hanoi(n-1, x, z, y); // 将x上编号为1至n-1的圆盘移动到y，z作辅助塔
move(x, n, z); // 将编号为n的圆盘从x移动到z
hanoi(n-1, y, x, z); // 将y上编号为1至n-1的圆盘移动到z，x作辅助塔
}
}
关于函数调用
通常，当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，系统需先完成三件事：
- 将所有的实在参数、返回地址等信息传递给被调用函数保存；
- 为被调用函数的局部变量分配存储区；
- 将控制转移到被调用函数的入口。
而从被调用函数返回调用函数之前，系统也要完成下面三件事情：
- 保存被调函数的计算结果；
- 释放被调函数的数据区；
- 依照被调函数保存的返回地址将控制转移到被调用函数。
当有多个函数构成嵌套调用时，按照“后调用先返回”的原则，上述函数之间的信息传递和控制转移必须通过“栈”来实现，即系统将整个程序运行时所需的数据空间安排在一个栈中，每当调用一个函数时，就为他在栈顶分配一个存储区，每当从一个函数退出时，就释放它的存储区，则当前正在运行的函数的数据区必在栈顶。
关于递归
一个递归函数的运行过程类似多个函数的嵌套调用，只是调用函数和被调用函数是同一个函数。
为了保证递归函数正确执行，系统需要设立一个递归工作栈，作为整个递归函数运行期间使用的数据存储区。
每一层递归所需信息构成一个“工作记录”，其中包括所有的实在参数、所有的局部变量以及上一层的返回地址。
- 每次进入一层递归，就产生一个新的工作记录压入栈顶。
- 每退出一层递归，就从栈顶弹出一个工作记录。
则当前执行层的工作记录必是递归工作栈栈顶的工作记录，称这个记录为活动记录，并称指示活动记录的栈顶指针为当前环境指针。
在调用函数与被调函数之间不一定传递参数的值，也可以传递参数的地址。
在利用允许递归调用的语言(例如C语言)进行对递归问题的编程时，不需要用户自己而由系统来管理递归工作栈。