C语言中递归函数的应用

史春水

摘要：该文对C语言递归函数的定义及调用进行了分析，就递归函数的应用以例题的形式进行了详细的讲解，便于初学者掌握递归函数分析思路与方法。

关键词：C语言；递归函数；递归调用；递归应用

中图分类号：TP3 文献标识码：A 文章编号：1009-3044（2018）28-0271-02

1 递归函数定义

在结构化程序设计中，一个函数在其定义中直接或间接地调用该函数本身的一种方法。在函数中直接调用函数本身，称为直接递归调用，如下图1所示。在函数中调用其他函数，其他函数又调用原函数，就构成了函数自身的间接调用，称为间接递归，如下图2所示：

2 递归函数的几个注意事项

（1）为求解规模为n的问题，设法将它分解成规模较小的问题，每次减少一个或几个元素，然后从这些较小的问题解进一步分解成另一个更少问题的解，并且这些规模较小的问题同样采用的相同的分解方法，分解成规模更小的问题，直到规模N=1或0时，能直接求解。

（2）递归算法：递归=递推+回归，分两个阶段。在递推阶段，把规模为n的问题求解化解为规模小于n的问题求解，依次减少一个或几个元素，直到规模N=1或0时，能直接求解。然后回归，推出n=2时解，推出n=3时解，........直到n的解。

（3）递归算法必需要有一个明确的出口。

（4）一般来说，递归需要三条件有：递归出口、有条件的递归前进段和同条件的递归返回段。

3 递归函数的几个典型应用

（1）应用一：求和问题

求1+2+3+4+5+6+.........+N的值。

分析：设sum（n）为前n项的和，则sum（n-1）为前n-1项的和，则有sum（n）=sum（n-1）+n；也就是说要求前n项的和，只要求前n-1项的和再加上n的值，求前n-1项的和只要求前n-2项的和再加上n-1的值，依次类推，直到n=1时，sum（n）=1，这就是递归函数出口，然后回归求sum（2）=sum（1）+2，依次类推求sum（n）；

源程序如下：

#include

int sum（int n）

{int t；

if（n==1） t=1；

else t=sum（n-1）+n；

return t；

}

main（）

{int n；

printf（“please input a number＼n”，&n;）；

printf（“1+2+3+4+.....+n=%d”，sum（n））；

getchar（）；

}

（2）应用二：猴子摘桃子问题

有一群猴子，去摘了一堆桃子，商量之后决定每天吃剩余桃子的一半，当每天大家吃完桃子之后，有个贪心的小猴都会偷偷再吃一个桃子，按照这样的方式猴子们每天都快乐地吃着桃子，直到第十天，当大家再想吃桃子时，发现只剩下一个桃子了，问：猴子们一共摘了多少桃子？

分析：设x1为前一天桃子数，设x2为第二天桃子数，则

x2=x1/2-1，变型为 x1=（x2+1）*2

x3=x2/2-1， 变型为x2=（x3+1）*2

以此类推： x前=（x后+1）*2 ；

源程序如下：

#include

int get（n）

{ int num； //定义所剩桃子数

if（n==10）

{return 1；

}

else

num = get（（n+1）+1）*2；

printf（"第%d天所剩桃子%d个＼n"， n， num）； //天数，所剩桃子个数

}

return num；

}

main（）

{ int num = get（1）；

printf（"猴子第一天摘了：%d个桃子。＼n"， num）；

getchar（）；

}

（3）应用三：求2个数的最大公约数问题

数学原理：设有两个数a和b，假设a比较大。令余数r = a% b。当r == 0时，即a可以整除num2，显然num2就是这两个数的最大公约数。当r ！= 0时，令a =b（除数变被除数），b = r（余数变除数），再做 r = a %b。递归，直到r == 0。

源程序如下：

#include

int maxgcd （int m，int n）

{ if（m%n==0）

return n；

else

return maxgcd（n，m%n）；

}

main（）

{ int a，b，temp；

printf（"please input two integer number："）；

scanf（"%d%d"，&a;，&b;）；

temp=maxgcd（a，b）；

printf（"The maxgys is %d＼n"，temp）；/*最大公約数*/

printf（"The min common multiple is %d＼n"，a*b/temp）；/*最小公倍数*/

getchar（）；

}

（4）应用四：组合问题

问题：找出从自然数1、2、……、n中任取r个数的所有组合。例如n=4，r=3的所有组合为。

分析：n=4，r=3的所有组合为

（1）4、3、2（2）4、3、1（3）4、2、1

（4）3、2、1

分析所列的10个组合，可以采用这样的递归来考虑。设函数为void ab（int n，int r）为找出从自然数1、2、……、n中任取r个数的所有组合。当组合的第一个数字选定时，其后的数字是从余下的n-1个数中取r-1数的组合。这就将求n个数中取r个数的组合问题转化成求n-1个数中取r-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字，约定函数将确定的r个数字组合的第一个数字放在a[r]中，当一个组合求出后，才将a[ ]中的一个组合输出。第一个数可以是n、n-1、……、r，函数将确定组合的第一个数字放入数组后，有两种可能的选择，因还未去顶组合的其余元素，继续递归去确定；或因已确定了组合的全部元素，输出这个组合。细节见以下程序中的函数ab。

源程序如下：

# include “stdio.h”

# define max 10

int x[max]；

void zuhe（int n，int r）

{ int i，j；

for （i=n；i>=r；i--）

{ x[r]=i；

if （r>1）

zuhe（i-1，r-1）；

else

{ for （j=x[0]；j>0；j--）

printf（“%3d”x[j]）；

printf（“＼n”）；

}

}

}

main（）

{ x[0]=3；

zuhe（4，3）；

}

（5）应用五： 爬楼梯问题

一个人上台阶可以一次上1个，2个，或者3个，问这个人上n层的台阶，总共有几种走法？

分析：第一次走有三种情况：走一步或者两步或者三步。若走一步，则是剩下 n-1个台阶；若走二步，则是剩下 n-2个台阶；若走三步，则是剩下 n-3个台阶；我们记f（n）表示下n层楼梯的方法总数，因为有三种方法可以走，那么有f（n）=f（n-1）+f（n-2）+f（n-3）这个递归公式，其中f（n-1）代表第一次走一步后的数目，f（n-2）代表第一次走两步后的数目，f（n-3）代表第一次走三步后的数目。利用递归思想，直至最后剩下的步数是1，2，3，作为递归终止条件。根据分析f（1）=1；f（2）=2，包括1+1和2；f（3）=4；包括1+1+1，1+2，2+1，3。

源程序如下：

#include

int fun（int n）

{

if（n == 1） return 1

else if（n==2） return 2；

else if（n==3） return 4；

else

return fun（n-1） + fun（n-2）+fun（n-3）；

}

void main（）

{int n；

scanf（"%d"， &n;）；

printf（"%d"， fun（n））；

getchar（）；

}

4 递归总结：递归算法的三个要求

一是每次在调用时，直接或间接调用函数本身，每次调用后在规模上有所减小，且分解问题的方法相同，这样在分析程序时本身就构成了一个循环；

二是相邻两次调用一定存在着紧密的联系，前一次（规模为n-1的问题）要为后一次（规模为n的问题）做准备，一般来说，前一次的输出应作为后一次的输入，前后二次调用紧密相关；

三是所有递归问题都可以用其他的算法来解决，但使用其他方法比较难解决，而使用函数的递归调用能很好地解决，分析思路清晰，且编写的程序简洁明了，又有较好的可读性；但由于在递归调用中，每次调用系統要为变量开辟内存空间、且每次调用要记住每一层调用后的返回点、这样势必增加许多额外的内存开销，因此函数的递归调用通常会降低程序的运行效率。

【通联编辑：代影】