for迴圈 VS 遞迴
所謂for迴圈也可以說成非遞迴(Non-Recursion),而遞迴(Recursion)非遞迴他們 之間的優缺,我由圖示來做個比較ˋ~~
| |
遞迴 |
非遞迴 |
| 優點 |
1.程式簡潔明確
2.節省記憶體空間
3.表達較強
4.區域變數與暫存變數較少
|
1.較節省執行時間
2.不需額外的Stack空間
|
| 缺點 |
1.執行時參數的存取較費時
2.需額外堆疊(Stack)空間支援
|
1.程式較長
2.浪費記憶體空間
3.表達力較弱
4.區域變數與暫存變數較多
|
舉個簡單例子~~
/*階乘用for*/
int main()
{
int math;
printf("請輸入一個整數:");
scanf("%d",&math);
int i,result=1;
for(i=1;i<=math;i++)
{
result = result * i;
}
printf("階乘為:%d",result);
}
很解單就解決了~
/*階乘用遞迴*/
int factorial(int); /*良好習慣,易讀,不亂*/
int factorial(int n)
{
if(n > 0)
return( n * factorial(n-1) );
else
return (1);
}
int main()
{
int math;
printf("請輸入一個整數:");
scanf("%d",&math);
printf("階成為:%d",factorial(math));
}
兩者比較下來,對於初學者來說,for比較好理解,所以我就先來解釋一下遞迴的一些觀念。
看過我的基本函數的朋友,多少會了解到結構的狀況,依個人喜好,
我喜歡先宣告玩int factorial(int);,
之後再用函數int factorial(int n){*********},
當然有它的好處,良好習慣,易讀,不亂....等等,為了面對以後的大程式,這樣也比較好看。
想用到factorial()函數,當然就要呼叫他, 再把一個整數丟進去factoral函式 ,例如我丟3:
1. 3>0,3*factorial(2),又被呼叫。
2. 2>0,2*factorial(1),,又被呼叫。
3. 1>0,1*factorial(0),變成0時n>0不成立;所以變成else的答案,factorial(0)=1。
4.知道factorial(0)=1後,將1,2,3,反推回去~~
5.factorial(3)就得出答案啦~~
打鐵趁熱再來一題~
/*最大公因數for*/
int main()
{
int m, n;
scanf("%d %d", &m, &n); //輸入兩值,空白隔開
while(n != 0)
{
int r = m % n;
m = n;
n = r;
}
printf("%d\n", m);
return 0;
}
先別往下滑,如果是遞迴呢?
/*最大公因數遞迴*/
int gcd(int,int);
int main()
{
int m, n;
scanf("%d %d", &m, &n);
printf("%d",gcd(m,n));
}
int gcd(int vm,int vn)
{
return( vn==0 ? vm : gcd(vn ,vm % vn) );
}
如果你食其味,再好好想想最小公倍數吧~~
/*最小公因數遞迴*/
int gcd(int vm, int vn) {
return(vn==0 ? vm : gcd(vn ,vm % vn));
}
int lcm(int m, int n) {
return m * n / gcd(m, n);
}
int main(void) {
int m, n;
scanf("%d %d", &m, &n);
printf("Lcm : %d\n", lcm(m, n));
return 0;
}
如果你用for迴圈寫最小公倍數,就有些亂~~
等到你出師,玩uva的題目時,就知道遞迴的好處。
留言列表
留言列表
