线性递归和迭代---分析阶乘

为了帮助更多编程者入门，我决定通过计算机程序解释与构造这本书上的例子来引出几个例子，帮助别人同时，也等于给自己复习，我们来看一个简单的例子----阶乘

     如果我问5的阶乘是多少，那么根据公式可以推倒出:5!=5*4*3*2*1 = 120

     这个算法其实很简单，实现如下:

     n! = n * (n -1) * (n - 2) ... * 3 * 2 * 1 ;

     仔细观察，不难发现一个通项公式: n * (n -1)  。

     于是，我们就很快可以照葫芦画瓢写出以下程序:   

#include <stdio.h>

int digui(int num)
{
	if(num == 0)
		return 1 ;
	if(num < 0)
		return -1 ;
	return num*digui(num-1) ;
}

/*
5!
5*4*3*2*1
5*(5-1)*(5-2)*(5-3)*(5-4)
*/
int main(void)
{
	int num = 0;
	int ret ;
	scanf("%d",&num);
	ret = digui(num) ;
	printf("%d\n",ret);
	return 0 ;
}

由分析可以得出，当num传参进digui()这个函数的时候，首先进行数据的校验，如果值等于1或者等于0时，直接返回1。

        然后继续看，如果num = 5 ;阶乘满足下面的递归关系（如果n ≥ 1）接下来计算机程序会被这么切：

       digui(5)  ---->  5 * digui(5 -1) = 20 ,此时num的值发生了改变，由5变成了4。

       digui(4)  ---->  5 * 4 * digui(4 -1) = 60 ,此时num的值发生了改变，由4变成了3。

       digui(3)  ---->  5 * 4 * 3 * digui(3 -1) = 120 ,此时num的值发生了改变，由3变成了2。

       digui(2)  ---->  5 * 4 * 3 * 2 *digui(2 -1) = 120 ,此时num的值发生了改变，由2变成了1。

       所以，最终的结果就是120。