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

劉卓亞

(云南機電職業技術學院工業信息技術系,云南昆明 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)。

4 結語

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

[1]衡軍山,邵軍.C語言程序設計基礎[M].航空工業出版社,2014.1.[2]彭順生.C語言項目式系統開發教程[M].人民郵電出版社,2016.8.