递归算法1

递归就是自己调用自己，它是设计和描述算法的一种有力工具，常常用来解决比较复杂的问题，能采用递归描述的算法通常有以下特征： 为求解规模为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: