1.4.2　n的階乘

計(jì)算n!的公式可以定義為

顯然，這是一個(gè)以遞歸技術(shù)定義的公式，在描述階乘算法時(shí)又用到階乘這一概念，因而很自然想到使用遞歸來(lái)實(shí)現(xiàn)該問(wèn)題，遞歸的停止條件是n=0。

遞歸算法描述如下：

     long long fun(int n)
       {
          if(n<0)
            cout<<"Illegal number!"<<endl;
         else if(n==0)
                return 1;
         else
                return n*fun(n-1);
     }

以n=3為例，fun（3）的運(yùn)行過(guò)程如圖1-2所示。

可見(jiàn)，fun（）在運(yùn)行中不斷調(diào)用自身從而降低規(guī)模，當(dāng)規(guī)模降為0時(shí)，即遞推到fun（0），此時(shí)滿足停止條件則停止遞推，開(kāi)始回歸（返回調(diào)用算法）并進(jìn)行計(jì)算，直到遞推開(kāi)始處，即求得fun（3）的值。

圖1-2　fun（3）的運(yùn)行過(guò)程示意圖