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