递归算法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");
c语言用递归函数求n的阶乘
}
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的阶乘*/ }
}
结果：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。