递归算法1——简单递归之求n的阶乘

递归就是自己调用自己，它是设计和描述算法的一种有力工具，常常用来解决比较复杂的问题，能采用递归描述的算法通常有以下特征：
为求解规模为N的问题，设法将它分解成规模较小的问题，从小问题的解容易构造出大问题的解，并且这些规模问题较小的问题也能采用同样的分解方法，分解成规模更小的问题，并能从这些更小问题的解构造出规模较大问题的解。一般情况下，规模N=1时，问题的解是已知的。

递归是一种分而治之、将复杂问题转换为简单问题的求解方法么。递归算法具有以下优缺点：

优点：使用递归编写的程序简洁、结构清晰，程序的正确性很容易证明，不需要了解递归调用的具体细节。

缺点：递归函数在调用的过程中，每一层调用都需要保存临时性变量和返回地址、传递参数，因此递归函数的执行效率低。

简单递归
求n的阶乘、斐波那契数列、求n个数的最大、数制转换、求最大公约数都属于简单递归。

求n的阶乘

【分析】
递归的过程分为两个阶段：回推和递推。回推就是根据要求解的问题找到最基本的问题解，这个过程需要系统栈保存临时变量的值；递推是根据最基本问题的解得到所求问题的解，这个过程是逐步释放栈的空间，直到得到问题的解。

求n的阶乘的过程分为回推和递推。

1.回推

求n的阶乘可以描述如下：
n!=n*(n-1)!
(n-1)!=(n-1)*(n-2)!
(n-2)!=(n-2)*(n-3)!
(n-3)!=(n-3)*(n-4)!
...
2!=2*1!
1!=0!
0!=1
1!=1

如果把n!写成函数形式，即f(n)，则f(5)就是表示5!。求5!的过程可以写成如下形式：
f(5)=5*f(4)
f(4)=4*f(3)
f(3)=3*f(2)
f(2)=2*f(1)
f(1)=1

从上述过程可以看出，求f(5)就需要调用f(4)，求f(4)就需要调用f(3)，求f(3)就需要调用f(2)，求f(2)就需要调用f(1)。其中f(5)、f(4)、f(3)、f(2)、f(1)都会调用同一个函数f，只是参数不同而已。上述递归调用的过程如图所示。

2.递推

根据f(1)这个最基本的已知条件，得到2!、3!、4!、5!，这个过程称为递推。由递推过程可以得到最终结果如图所示。

综上所示，回推的过程是将一个复杂的问题变为一个简单的问题，递推的过程是由简单的问题得到复杂问题的解。

【算法描述】

通过上述分析可知，当n=0或n=1时，n的阶乘即f(n)=1；否则，n的阶乘即f(n)=n*f(n-1)。因此公式为：

其实就是一个递归定义的公式。

code:

#include<stdio.h>
#include <iostream>
long int Fact(int n);
void main()
{
	int n;
	printf("请输入一个整数:");
	scanf("%d", &n);
	printf("%d!=%d\n", n, Fact(n));
	system("pause");
}
long int Fact(int n)
{
	int x;
	long int y;
	if (n < 0)                  	/*n<0时阶乘无定义*/
	{
		printf("参数错!");
		return -1;
	}
	if (n == 0)					/*n==0时阶乘为1*/
		return 1;
	else
	{
		return n*Fact(n - 1);		/*递归求n的阶乘*/
	}
}

结果：