基于C语言的递归算法研究

2018-06-14刘卓亚

数字技术与应用 2018年3期

刘卓亚

(云南机电职业技术学院工业信息技术系,云南昆明 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。

由公式: c%d<=c/2 可知:每次递归调用,问题的规模减小一半,类似于二分查找,这显然是一个非常好的算法。

由于程序前4行,花费的时间为常量时间,在第5行进行递归调用,问题规模减少一半。可得出,T(N) = T(N/2)+O(1) 推出:时间复杂度为O(logN)。

3 利用循环语句求解最大公约数

穷举法,也叫枚举法。穷举法求两个正整数的最大公约数就是利用循环语句进行求解,其解题步骤:从两个数中较小数开始由大到小列举,直到找到公约数立即中断列举,得到的公约数便是最大公约数。

C语言的源代码如下:

int divisor (int a1,int b1) /*自定义函数求两数的最大公约数*/

{

int temp; /*定义整型变量*/

temp=(a1>b1)b1:a1; /*采种条件运算表达式求出两个数中的最小值*/

while(temp>0)

{

if (a1%temp==0&&b1%temp==0) /*只要找到一个数能同时被a,b所整除,则中止循环*/

break;

temp--;/*如不满足if条件则变量自减,直到能被a,b所整除*/

}

return (temp); /*返回满足条件的数到主调函数处*/

}

#include "stdio.h"

main()

{

int c,d,t;

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

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

t1=divisor(c,d);

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

}

如果输入的两个数仍然是8和6,则temp=6,由于6不能同时被8和6整除,所以temp=5,5不能同时被8和6整除,temp=4,4不能同时被8和6整除,temp=3,3不能同时被8和6整除,temp=2,2能同时被8和6整除,因此2就是8和6的最大公约数。该程序只有一层循环,时间复杂度为O(N)。