长篇鬼故事 - 递归函数例子 C语言递归函数的执行与求解

　　导语：函数的递归调用是在调用一个函数的执行过程中，直接或间接地调用该函数本身，使用递归函数的程序结构清晰，简单、易懂。下面就由小编为大家介绍一下C语言递归函数的执行与求解，欢迎大家阅读!

　　1 递归函数

　　C语言的特点之一就在于允许函数的递归调用，即允许在函数内部直接或间接的调用函数自身，被调用的函数被称为递归函数。递归调用有直接递归调用和间接递归调用两种形式，递归函数常用于解决那些需要分多次求解且每次求解过程都基本类似的问题。构造递归函数的关键在于寻找递归算法和终结条件。递归算法就是解决问题所采取的方法和步骤，一般只要对问题的若干次求解过程进行分析和归纳，找出每一次求解过程之间的规律性，就可归纳出递归算法，终结条件是为了终结函数的递归调用而设置的一个条件或规则。递归调用的一般形式为：

　　函数类型 函数名(参数列表)

　　{

　　，，，，，

　　函数名(参数列表)

　　…..

　　}

　　2 递归条件

　　使用递归调用编写程序时，要注意以下几点：

　　(1)可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式，只是所处理的对象具有一定的规律性。也就是说解决问题的方法相同，调用函数的参数有规律的递增或递减。

　　(2)递归函数必须有一个终止处理条件，即必须有一个明确的结束条件，必须在适当的时候能够结束递归调用，否则会使程序陷入死循环，导致系统崩溃。

　　(3)有些使用递归算法求解的问题也可使用普通循环算法来实现，相较于循环程序，递归程序结构简单，逻辑清晰，但运行效率低，故在有其他算法可以代替的情况下，要尽量避免使用递归算法编写程序。

　　3 递归实例

　　例：使用递归方法求n!。

　　在数学上n!=1×2×3×…×n-1×n，我们可以写成以下形式

　　1 当n=0或n=1时

　　n!=

　　(n-1)!×n 当n>1时

　　根据以上形式，可以写出如下递归调用程序：

　　int f(n)

　　{

　　if(n==1||n==0)

　　return 1;

　　else

　　return f(n-1)*n;

　　}

　　int main()

　　{

　　int n;

　　scanf(“%d”，&n);

　　if(n<0)

　　printf(“data error!”);

　　else

　　printf(“%d”，f(n));

　　return 0;

　　}

　　4 递归函数执行过程

　　递归调用之所以能够实现，是因为函数在每一次执行过程中，都会把自己所有形参变量和局部变量复制一个副本，压入栈中，这些副本分别位于栈中不同的内存空间，和函数的其他执行过程毫不相干，这种机制使得递归调用成为可能。一个递归函数的执行过程类似于调用函数和被调用函数是同一个函数的多层嵌套调用，因此，和递归函数的执行过程密切相关的一个重要概念就是递归函数运行的层次。假设调用该递归函数的主函数为第0层，则从主函数调用递归函数则进入第一层;从第n层调用本函数则进入“下一层”，即第n+1层。反之，退出第n层递归调用应返回至“上一层”，即第n-1层。

　　在递归函数的执行过程中，另一个非常重要的概念是“递归工作栈”的使用，当一个函数(调用者)调用另外一个函数(被调用者)时，系统会把调用者的所有实在参数，被调用者的形式参数、局部变量，以及调用者的返回地址等信息全部压入“递归工作栈”暂存，当被调用者执行完毕时，系统会从栈中弹出被调用者的形式参数和局部变量，释放被调用者所占用的数据区，接着被调用者返回，然后系统从栈中弹出调用者的返回地址，和实在参数等信息，此时调用者函数可以继续执行下去。

　　5 求解方法

　　我们通过举例来说具体说明递归函数的求解，比如在主函数中输入n的值为5，即求5!，则函数的求解过程可以用图1-1表示：

　　以上问题的具体求解过程描述如下：①调用函数f(5)，n=5，函数f(5)的返回结果是f(4)*5，系统暂存f(5)的形参和中间计算结果，然后转去调用函数f(4)。②执行函数f(4)，n=4，函数f(4)的返回结果是f(3)*4，系统暂存f(4)的形参和中间计算结果，然后转去调用函数f(3)。③执行函数f(3)，n=3，函数f(3)的返回结果是f(2)*3，系统暂存f(3)的形参和中间计算结果，然后转去调用函数f(2)。④执行函数f(2)，n=2，函数f(2)的返回结果是f(1)*2，系统暂存f(2)的形参和中间计算结果，然后转去调用函数f(1)。⑤执行函数f(1)，n=1，函数f(1)返回结果1，f(1)执行完毕，系统释放f(1)的形参和中间变量所占的数据区，然后返回到调用函数f(1)处。⑥函数f(2)返回结果f(1)*2=1*2=2，f(2)执行完毕，系统释放f(2)的形参和中间变量所占的数据区，然后返回到调用函数f(2)处。⑦函数f(3)返回结果f(2)*3=2*3=6，f(3)执行完毕，系统释放f(3)的形参和中间变量所占的数据区，然后返回到调用函数f(3)处。⑧函数f(4)的返回结果f(3)*4=6*4=24，f(4)执行完毕，系统释放f(4)的形参和中间变量所占的数据区，然后返回到调用函数f(4)处。⑨函数f(5)返回结果f(4)*5=24*5=120，f(5)执行完毕，系统释放f(5)的形参和中间变量所占的数据区，然后返回到调用函数f(5)处，即main函数，此问题求解结束。

　　6 结束语

　　函数的递归调用，可以把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归算法只需用少量的程序就可描述出解题过程所需要的多次重复计算，大大减少了程序的代码量并增强了程序的可读性。但在求解过程中容易出错和混淆，了解递归函数的执行过程，并借助于图示化的方法、，即可正确、快速求解递归函数。