iT邦幫忙

2021 iThome 鐵人賽

DAY 14
0
Software Development

0基礎也看得懂的程式設計-30天學會C語言系列 第 14

30天學會C語言: Day 13-遞迴體驗鎮魂曲

遞迴

在函式裡面可以呼叫函式本身

下面例子中,fun() 會先將參數 x 顯示到視窗上,之後判斷 x 是不是不等於0,若不等於0則呼叫 fun(x-1),如果等於0則不做任何動作(因為之後沒有內容了,所以函式會結束)

#include<stdio.h>
#include<stdlib.h>

void fun(int x){
	printf("%d ", x);
	if(x!=0)
		fun(x-1);
}

int main(){
	fun(5);

	return 0;
}

所以這段程式執行時,main() 會先呼叫 fun(5),在函式 fun() 中:

  1. 會先顯示 x(5)到視窗上,因為 x 不等於0,所以會呼叫 f(x-1),也就是 f(4)
  2. 顯示 x(4)到視窗上,因為 x 不等於0,所以會呼叫 f(x-1),也就是 f(3)
  3. 顯示 x(3)到視窗上,因為 x 不等於0,所以會呼叫 f(x-1),也就是 f(2)
  4. 顯示 x(2)到視窗上,因為 x 不等於0,所以會呼叫 f(x-1),也就是 f(1)
  5. 顯示 x(1)到視窗上,因為 x 不等於0,所以會呼叫 f(x-1),也就是 f(0)
  6. 顯示 x(0)到視窗上,因為 x 等於0,不執行任何動作,fun() 會結束並回到 main()

這樣類似迴圈可以重複的效果稱為遞迴(Recursion)

遞迴的優點

遞迴執行時花費的資源可能比用迴圈還大,設計時可能也比迴圈還難,但遞迴還是有迴圈無法達到的優點

迴圈中如果有用到其他幾次計算的結果,需要另外用一個陣列將每次的執行結果記錄下來
例如費波那契數列,這個數列的第一項(x=0)是0和第二項(x=1)為1,之後的每一項都是前兩項的和,也就是:

如果用迴圈,必須搭配一個陣列紀錄每個 F() 的值

#include<stdio.h>
#include<stdlib.h>

int main(){
	int n, f[100];
	scanf("%d", &n);
	for(int i=0; i<=n; i++){
		if(i==0)
			f[i]=0;
		else if(i==1)
			f[i]=1;
		else
			f[i]=f[i-1]+f[i-2];
	}
	printf("%d\n", f[n]);

	return 0;
}

用遞迴編寫程式時更加直觀
這裡的 F() 可以不用 if elseelse,因為執行的內容都是 return,會強制結束函式
所以對第一個 if() 來說,如果條件符合會執行 return 0,後面的內容被不會執行,如果條件不符才會執行後面的內容,對第二個 if() 來說也是,也就是說只有前兩個的條件都不符才會執行最後一行,如果前面的條件符合了也一定不會執行後面的內容,所以可以確定這三個 return 一定只會執行其中一個

#include<stdio.h>
#include<stdlib.h>

int F(int x){
	if(x==0)
		return 0;
	if(x==1)
		return 1;
	return F(x-1)+F(x-2);
}

int main(){
	int n;
	scanf("%d", &n);
	printf("%d\n", F(n));

	return 0;
}

另外遞迴也常和一些資料結構一起使用,之後會有相關範例,這個就下次再說吧!


上一篇
30天學會C語言: Day 12-自訂函式
下一篇
30天學會C語言: Day 14-全部包軌!
系列文
0基礎也看得懂的程式設計-30天學會C語言30

尚未有邦友留言

立即登入留言