函數(一） 自訂函數、遞迴函數 2008.10. 綠園

什麼是函數？ 函數是 C / C++ 語言的基本模組，也就是說所有的 C / C++ 程式碼都是由函數組成的。 其目的就是利用模組化的方式簡化主程式，也可以節省撰寫相同程式的時間。 每一個 C / C++ 程式至少包括一主函數 main( )。 函數包括－－ 系統函數：位於系統函數庫內，使用時須在程式的開頭用 #include <標頭檔> 自定函數：使用時如變數一般，須宣告。

函數的宣告(一) int add (int, int); 有兩個引數傳入 add() 函數，型態均為int，各型態間以逗號分開 傳回值型態是整數 int add (int, int); 函數名稱為add

函數的宣告(二) 函數沒有傳回值 函數不需要有引數傳入 void star (void); 函數名稱為star

練習：試寫一函數void star(void), 當主程式呼叫star()時，螢幕上會顯示出13個星號 ”*************” 。 #include <iostream> using namespace std; void star(void); //宣告star( )函數的型態 int main( ) { star( ); //呼叫star( ) 函數 cout << “歡迎使用ｃ++！\n”; star( ); return 0; } void star(void) //定義star( )函數的內容 cout << “*************\n”; return;

函數的用法 7 9 9 7 9 a b max( a, b ) j i return i or j /* 傳回較大值 */ #include <iostream> using namespace std; int max(int,int); /* 宣告函數max() */ int main(void) { int a,b; cout << "First number:"; /*輸入兩個整數*/ cin >> a; cout << "Second number:"; cin >> b; cout << "The larger number is " << max(a,b) << endl; /*印出較大值*/ return 0; } int max(int i,int j)/* 自訂函數max(),傳回較大值 */ if (i>j) return i; else return j; a b 7 9 max( a, b ) 9 j 7 i 9 return i or j

函數的寫法 int max(int i, int j) /*自訂函數max(),傳回較大值*/ { if (i>j) /* 傳回較大值 */ #include <iostream> using namespace std; int max(int, int); /*宣告函數max()*/ int main(void) { int a,b; cout << "First number:"; /*輸入兩個整數*/ cin >> a; cout << "Second number:"; cin >> b; cout << "The larger number is " << max(a,b) << endl; /*印出較大值*/ return 0; } int max(int i, int j) /*自訂函數max(),傳回較大值*/ { if (i>j) return i; else return j; }

函數的宣告 int max(int, int); /*宣告函數max()*/ /* 傳回較大值 */ #include <iostream> using namespace std; int max(int, int); /*宣告函數max()*/ int main(void) { int a,b; cout << "First number:"; /*輸入兩個整數*/ cin >> a; cout << "Second number:"; cin >> b; cout << "The larger number is " << max(a,b) << endl; /*印出較大值*/ return 0; } int max(int i,int j) /* 自訂函數max(),傳回較大值 */ if (i > j) return i; else return j;

其他範例—求兩數相加 int add(int,int); /* 宣告函數add() */ /* 兩數相加 */ #include <iostream> using namespace std; int add(int,int); /* 宣告函數add() */ int main(void) { int a,b; cout << "First number : "; /* 輸入兩個整數 */ cin >> a; cout << "Second number : "; cin >> b; cout << "The sum of " << a << " and " << b << " is " << add(a,b) << endl; /*印出sum值*/ return 0; } int add(int num1, int num2) /* 自訂函數add(),傳回兩數的和 */ int sum; sum = num1 + num2; return sum; (2) (1) (3)

其他範例—求最大公因數 int gcd(int,int); /* 宣告函數gcd() */ /* 最大公因數 */ #include <iostream> using namespace std; int gcd(int,int); /* 宣告函數gcd() */ int main(void) { int a,b; cout << "First number : "; /* 輸入兩個整數 */ cin >> a; cout << "Second number : "; cin >> b; cout << "The GCD of " << a << " and " << b << " is " << gcd(a,b) <<endl; /*印出gcd值*/ return 0; } int gcd(int i, int j) /* 自訂的函數gcd(),傳回最大公因數 */ int g; while(j!=0) g=i%j; i=j; j=g; return i;

遞迴函數 遞迴：函數呼叫自己的過程，稱為遞迴。(Recursion) 遞迴函數：具備遞迴性質的函數，稱為遞迴函數(Recursive Function)。 典型的範例：費氏數列

費氏數列(Fibonacci) 數列中，任意數為前兩數之和。 即，an = an-1 + an-2 唯 a0 = 1, a1 = 1

試設計一程式，可印出費氏數列至第n項 假設f(x)函數為費氏數列的第x項值。 則數列中的第 n 項寫成函數型態，即為f(n)。 欲求f(n)，可寫成 f(n) = f(n-1) + f(n-2) 這是一個遞迴式，必須有Ending 條件， 即 f(1) = 1， f(2) = 1。 程式寫法如下：

#include <iostream> using namespace std; int fib(int); //宣告fib函數的型態 int main(void) //主程式 { int N,i; cout << "N = ? "; cin >> N; for (i=1; i<=N; i++) //循序印出f(1) 到 f(n) cout << fib(i) << endl ; return 0; } int fib(int n) //定義fib(n) { if (n==1 || n==2) //函數的Ending 值設定 return 1; else return (fib(n-1) + fib(n-2)); //函數的一般值設定 } (2) (1) (3)

看f(6)的執行序 F(6) F(5) F(4) F(3) F(2) F(4) F(3) F(3) F(2) F(2) F(1) F(2)

看f(6)的執行序 n if(n==1 || n==2) Return 結果 6 false F(5)+f(4) 8 5 F(4)+f(3) true 1 1 1 true 1 1

練習：試寫一power(a,b)函數，可算出 ab的值。 Hint: ab = a * ab-1 　寫成函數形式： 　　power(a,b) = a * power(a, b-1) 　Ending 條件： a0 = 1 　所以.. 　1, when b=0 　power(a,b) = 　 a*power(a,b-1) , when b>1

練習：試以遞迴函數型態，改寫最大公因數程式 Hint.. b, if (a % b == 0) gcd(a,b)= gcd(b, a%b), if (a%b != 0)