1.4.2　n的阶乘

计算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）的运行过程如图1-2所示。

可见，fun（）在运行中不断调用自身从而降低规模，当规模降为0时，即递推到fun（0），此时满足停止条件则停止递推，开始回归（返回调用算法）并进行计算，直到递推开始处，即求得fun（3）的值。

图1-2　fun（3）的运行过程示意图