3.3 栈的典型应用与递归算法

3.3.1 栈的典型应用——子程序的调用和返回

栈的典型应用之一是子程序的调用和返回，一个程序可以由多个子程序（C语言为函数）构成，其中的一个子程序可以调用另一个子程序，这种调用者和被调用者之间的联系（衔接）就是通过堆栈实现的。程序控制在调用者和被调用者之间转换时，系统要做以下几件事情。

（1）将当前调用者的所有实参、临时（局部）变量、调用子程序后的返回地址等保存起来。

（2）为被调用者的局部变量分配存储空间。

（3）转向被调用者执行。

当程序中存在多层次的嵌套调用时，从被调用者返回调用者的顺序是后调用的先返回，这种调用、返回关系符合堆栈的特点，可以借助于堆栈来实现。当程序从调用者转向被调用者时，系统将调用者的所有实参、临时（局部）变量、调用子程序后的返回地址等压入堆栈，称为保护现场；调用结束，系统再执行出栈操作，称为恢复现场，并根据出栈后得到的返回地址返回到调用者继续运行。

以下C程序中，main函数调用了fun1，fun1又调用了fun2，这三者之间的调用与返回就是通过堆栈的进栈、出栈操作实现的。如图3-6所示是函数的嵌套调用示意图。

int fun1(int p);
int fun2(int p1,int p2);
main()
{ int n,result;
…

   result=fun1(n);
   …
}
fun1(int p)
{ int n1,n2,result;
   …
   result=fun2(n1,n2);
   …
}
fun2(int p1,int p2)
{
   …
}

3.3.2 递归算法

存在直接或间接调用自身（己）的算法称为递归算法，又称为自调用算法。递归过程是借助于堆栈实现的，只不过这个过程是系统内部自动完成的，递归可分为直接递归与间接递归。

（1）直接递归。算法直接调用自身，如图3-7（a）所示。

（2）间接递归。一个算法在调用另一算法时，另一算法又产生了对该算法的调用，如图3-7（b）所示。

以下是根据公式：

求解n!的递归算法。

long fun(int n)
{  long y;
   if(n==1)
       return(1);
   else
   {  y=fun(n-1);
      return(n*y);
   }
} /* fun */

递归算法由递归出口和递归体两部分组成，上述求n!的递归算法中，n!=1（n=1时）为递归出口，n!=n×(n-1)!（n>1时）为递归体。

递归算法的分析设计是自顶向下的求解过程。对于一个不易直接求解的大问题，将其转化成一个或几个有同样求解过程的小问题来解决，再把这些小问题进一步分解为更小的小问题来解决，如此分解，直至每个小问题都可以直接解决（到达递归出口）为止。

3.3.3 递归算法的执行过程

仍然以求n!的算法为例，进一步分析该算法的执行过程。递归算法本质上是函数的嵌套调用，只是此处的被调函数是自己，每一次的嵌套调用改变的只是函数的参数，以fun(4)为例，其执行过程如图3-8所示，相应的系统内部栈的工作过程如图3-9所示。

【例3-8】对下面的递归算法，写出调用f(4)的执行结果。

void f(int k)
{
    if(k>0)
        {
          printf(k);
          f(k-1);
          f(k-1);
        }
} /*f*/

f(4)的执行过程可用图3-10表示，图中从左到右的缩进是递归的嵌套调用，同一层次自上而下是顺序关系。由此可知f(4)的执行结果是输出15个值：

4,3,2,1,1,2,1,1,3,2,1,1,2,1,1