基于C語言的遞歸算法研究

劉卓亞

(云南機電職業(yè)技術(shù)學院工業(yè)信息技術(shù)系,云南昆明 650203)

遞歸是C語言中經(jīng)常使用的將復雜問題簡單解決的方法,遞歸作為一種算法在程序設(shè)計語言中廣泛應(yīng)用。C語言中當一個函數(shù)直接或間接調(diào)用該函數(shù)本身時,就被稱為函數(shù)的遞歸調(diào)用。遞歸的基本思想是將原問題轉(zhuǎn)化為規(guī)?？s小了的同類問題的子問題,然后遞歸調(diào)用該函數(shù)來表示問題的解[1]。

1 遞歸調(diào)用的條件

在解決實際問題時,能否用遞歸的方法來解決,取決于問題自身的特點。一個問題要用遞歸的方法來解決,需滿足以下條件:

(1)原問題可轉(zhuǎn)化為一個新問題,而這個新問題與原問題有相同的解決方法。

(2)新問題可繼續(xù)這種轉(zhuǎn)化,在轉(zhuǎn)化過程中,問題有規(guī)律地遞增或遞減。

(3)在有限次轉(zhuǎn)化后,問題得到解決,即具備遞歸結(jié)束的條件。

2 利用遞歸求解最大公約數(shù)

C語言中用遞歸方式計算兩個正整數(shù)a1,b1的最大公約數(shù),實質(zhì)它依賴于下面的定理:

從該定理我們可以看出它是符合上述條件的,首先將求解最大公約數(shù)gcd(a1,b1)轉(zhuǎn)化成了一個新問題gcd(b1,a1 mod b1),而這個新問題與原問題有相同的解決方法;其次第二個參數(shù)經(jīng)過多次取余后一直在變小;經(jīng)過有限次的調(diào)用后b1=0,出現(xiàn)遞歸邊界,結(jié)束遞歸調(diào)用。

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("請輸入兩個整數(shù):");

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

t1=gcd(c,d);

printf("最大公約數(shù)是 %d ",t);/*最大公約數(shù)*/

}

如果輸入的兩個數(shù)是8和6,需要計算gcd(8,6)由于6不是邊界值,需要計算gcd(6,2),由于2也不是邊界值,需要計算gcd(2,0),此時出現(xiàn)邊界值,gcd(2,0)的結(jié)果是2,向上返回gcd(6,2)的結(jié)果也是2,再向上返回gcd(8,6)的結(jié)果也是2,最后求得8和6的最大公約數(shù)是2。

由公式: c%d<=c/2 可知:每次遞歸調(diào)用,問題的規(guī)模減小一半,類似于二分查找,這顯然是一個非常好的算法。

由于程序前4行,花費的時間為常量時間,在第5行進行遞歸調(diào)用,問題規(guī)模減少一半?？傻贸?T(N) = T(N/2)+O(1) 推出:時間復雜度為O(logN)。

3 利用循環(huán)語句求解最大公約數(shù)

窮舉法,也叫枚舉法。窮舉法求兩個正整數(shù)的最大公約數(shù)就是利用循環(huán)語句進行求解,其解題步驟:從兩個數(shù)中較小數(shù)開始由大到小列舉,直到找到公約數(shù)立即中斷列舉,得到的公約數(shù)便是最大公約數(shù)。

C語言的源代碼如下:

int divisor (int a1,int b1) /*自定義函數(shù)求兩數(shù)的最大公約數(shù)*/

{

int temp; /*定義整型變量*/

temp=(a1>b1)b1:a1; /*采種條件運算表達式求出兩個數(shù)中的最小值*/

while(temp>0)

{

if (a1%temp==0&&b1%temp==0) /*只要找到一個數(shù)能同時被a,b所整除,則中止循環(huán)*/

break;

temp--;/*如不滿足if條件則變量自減,直到能被a,b所整除*/

}

return (temp); /*返回滿足條件的數(shù)到主調(diào)函數(shù)處*/

}

#include "stdio.h"

main()

{

int c,d,t;

printf("請輸入兩個整數(shù):");

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

t1=divisor(c,d);

printf("最大公約數(shù)是 %d ",t);

}

如果輸入的兩個數(shù)仍然是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的最大公約數(shù)。該程序只有一層循環(huán),時間復雜度為O(N)。

4 結(jié)語

通過上述對比,我們發(fā)現(xiàn)一般情況下遞歸和循環(huán)語句是可以相互替換的,從語法來看遞歸比循環(huán)語句更簡潔,但是從算法上看,循環(huán)語句更容易理解,而遞歸需要找到遞歸形式和遞歸邊界,這對于初學者來說是比較困難的。從執(zhí)行的效率來看,遞歸調(diào)用比循環(huán)語句更高效。

[1]衡軍山,邵軍.C語言程序設(shè)計基礎(chǔ)[M].航空工業(yè)出版社,2014.1.[2]彭順生.C語言項目式系統(tǒng)開發(fā)教程[M].人民郵電出版社,2016.8.