栈与递归(C语言实现)

我们已经知道了栈的定义以及有了对栈的基本应用,我们现在就要进一步对栈的应用有更深入的了解。

递归,就是在定义自身的同时又出现了对自身的调用。而递归又分为两种,直接和间接。直接是在定义函数体内直接调用自己,而间接则是经过一系列中间调用函数语句,通过其他函数间接调用自己。

事实上,递归的实现是在栈的基础上实现的。(这个事情之后会提)

那么有哪些我们熟悉的递归呢?斐波那契数列肯定是我们会第一个想到的。其次是阿克曼函数,可能这个函数会有些生疏。

上述 Ackerman 函数可用一个简单的 C 语言函数描述如下: 
int ack(int m,int n) 
{  
    if(m==0) 
        return n+1;  
    else if (n==0) 
        return ack(m-1,1); 
    else return ack(m-1, ack(m,n-1)); 
} 

当然还要一个非常非常经典的题目,汉诺塔问题
n阶Hanoi塔问题:假设有三个分别命名为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上。而如何将n-1个圆盘从一个塔座移至另一个塔座问题是一个和原问题具有相同特征属性的问题,只是问题的规模小于1,因此可以用同样方法求解。由此可得如下求解n阶Hanoi塔问题的递归算法

void hanoi(int n, char x, char y, char z) 
/* 将塔座X上从上到下编号为1至n,且按直径由小到大叠放的n个圆盘,按规则搬到塔座Z上,Y用作辅助塔座。*/ 
{ 
   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作辅助塔 */  
   } 
}  

事实上,我们就可以得出一些递归问题算法的得出规律。
使用递归算法的前提有两个:
⑴原问题可以层层分解为类似的的子问题,且子问题比原问题的规模更小。
⑵规模最小的子问题具有直接解。

设计递归算法的方法是:
⑴寻找分解方法:将原问题转化为子问题求解。( 例:n!=n*(n-1)! )
⑵设计递归出口:即根据规模最小的子问题,确定递归终止条件。(例:求解 n!时,当 n=1 时,n!=1)。

那么在递归实现的时候都发生了些什么呢?
递归过程的实现递归进层(i→i +1 层)系统需要做三件事:
⑴ 保留本层参数与返回地址;
⑵ 为被调用函数的局部变量分配存储区,给下层参数赋值;
⑶ 将程序转移到被调函数的入口。
而从被调用函数返回调用函数之前,递归退层(i←i +1 层)系统也应完成三件工作:
⑴ 保存被调函数的计算结果;
⑵ 释放被调函数的数据区,恢复上层参数;
⑶ 依照被调函数保存的返回地址,将控制转移回调用函数。

通过这些,我们也应该可以看到,其实递归的操作是十分多的,也就是说递归算法的效率其实很低。那么我们要如何将递归改为非递归呢?其实我们可以根据问题来实现用循环来实现递归,就好比斐波那契循环,其实用循环可以很容易实现。

ok,栈到这里就结束啦。接下来是队列。