刘卓亚

(云南机电职业技术学院工业信息技术系,云南昆明 650203)

递归是C语言中经常使用的将复杂问题简单解决的方法,递归作为一种算法在程序设计语言中广泛应用。C语言中当一个函数直接或间接调用该函数本身时,就被称为函数的递归调用。递归的基本思想是将原问题转化为规模缩小了的同类问题的子问题,然后递归调用该函数来表示问题的解[1]。

1 递归调用的条件

在解决实际问题时,能否用递归的方法来解决,取决于问题自身的特点。一个问题要用递归的方法来解决,需满足以下条件:

(1)原问题可转化为一个新问题,而这个新问题与原问题有相同的解决方法。

(2)新问题可继续这种转化,在转化过程中,问题有规律地递增或递减。

(3)在有限次转化后,问题得到解决,即具备递归结束的条件。

2 利用递归求解最大公约数

C语言中用递归方式计算两个正整数a1,b1的最大公约数,实质它依赖于下面的定理:

从该定理我们可以看出它是符合上述条件的,首先将求解最大公约数gcd(a1,b1)转化成了一个新问题gcd(b1,a1 mod b1),而这个新问题与原问题有相同的解决方法;其次第二个参数经过多次取余后一直在变小;经过有限次的调用后b1=0,出现递归边界,结束递归调用。

C语言的源代码如下:

int gcd (int a1,int b1)

{ if(a1%b1==0)

return b1;

else

return gcd(b1,a1%b1);

}

#include "stdio.h"

main()

{

int c,d,t;

printf("请输入两个整数:");

scanf("%d%d",&c,&d);

t1=gcd(c,d);

printf("最大公约数是 %d ",t);/*最大公约数*/

}

如果输入的两个数是8和6,需要计算gcd(8,6)由于6不是边界值,需要计算gcd(6,2),由于2也不是边界值,需要计算gcd(2,0),此时出现边界值,gcd(2,0)的结果是2,向上返回gcd(6,2)的结果也是2,再向上返回gcd(8,6)的结果也是2,最后求得8和6的最大公约数是2。……