Coding Prep 演算法資料結構教學

函數呼叫與遞迴 (function call and recursion)

函數呼叫與遞迴 (function call and recursion)

函數 (function)

其實在這之前，大家應該都已經用過函數 (function) 了，只是大家用的應該都是別人寫好的 function，例如 abs(), sqrt()。
現在就來教大家怎麼自己寫 function !

Function 出現的位置是在 int main() 之前，並且在 #include, #define, using namespace等的下面。一個函數的架構就是下面那樣。

#include <bits/stdc++.h>
using namespace std;
回傳型態 函數名稱(參數){
     要做的事
　　　return 回傳值;
}
int main() {
}

回傳型態可以是我們之前提到的 int, bool, float, int [], vector <int> 等都可以。

參數則是你想要把甚麼資料傳入給函數。因為如果你的變數開在 main 裡面，這個函數是得不到的，必須要透過參數把它傳入函數裡面，函數才可以使用。

這邊可能是大家第一次接觸到 “回傳” 這個東西。其實回傳不複雜。回傳的功能就是是在呼叫函數時，可以透過回傳把運算完的結果傳回去給呼叫的地方。所以，回傳值得型態必須要跟回傳型態是一樣的。注意！在 return 之後的所有程式碼都不會被執行，因為函數已經結束了！

例如，今天假如我的函數是想把兩個數字加起來，我可以這樣寫。在 main 裡面用函數的操作叫做呼叫那個函數。

#include <bits/stdc++.h>
using namespace std;
int add(int a, int b){
    return a + b;
    cout << "Hi\n"; // 不會被執行
}
int main() {
    int a = 5, b = 3;
    cout << add(5, 3) << '\n';
}

另外，如果函數的功能並不需要回傳任何東西的話，可以將回傳型態設定成 void。回傳型態是 void 的話就不用 return 任何東西，但是還是可以單打一個 return;　可以比較方便離開函數，例如下面的例子：

#include <bits/stdc++.h>
using namespace std;
void print(string s){
    if(s.empty()) return;
    cout << "Hello, " << s << '\n';
}
int main() {
    cout << print("World") << '\n';
}

聰明如你們可能會發現，main 長得跟函數一模一樣。而沒錯！main 也是一個函數，他是整個程式的主函數！

區域變數和全域變數

在學習完這些之後，我們需要更了解區域變數和全域變數的差別。

  • 區域變數的有效範圍只有在函數裡面而已，宣告在函數裡面
  • 全域變數則是在整個檔案裡都可以用，宣告在函數外面（main以上，#include, #define, using namespace 等的下面)
  • 如果有同樣名字的一個全域變數以及區域變數存在的話，程式會取用區域變數

在遇到需要用到很大的變數例如，二維陣列等，建議可以開在全域，避免把它用參數傳進去會花比較多時間。

函數內的更改

還有一點要注意的是，如果在函數內更改參數的值，實際上，在原本的地方那些值是不會被改變的，因為函數在執行是會自己 copy 一份，並拿那份來用。

如果想要更改的話，就必須加上取地址符 (&) 才可以更改到。詳細的內容 APCS 實作的部分是不會考到，只須記得就好！

例如以下的例子，第一個函數並不會改到任何東西，第二個才會。

#include <bits/stdc++.h>
using namespace std;
void swap(int a, int b){
    int tmp = a;
    a = b;
    b = tmp;
}
void swap2(int &a, int &b){
    int tmp = a;
    a = b;
    b = tmp;
}
void print(int a, int b){
    cout << a << ' ' << b << '\n';
}
int main() {
    int a = 1, b = 2;
    swap(a, b);
    print(a, b);
    swap2(a, b);
    print(a, b);
}

輸出：

1 2
2 1

遞迴 (Recursion)

遞迴是一種特別的函數，他會在函數中自己呼叫自己。這樣講可能有點抽象，我們來看一個例子

#include <bits/stdc++.h>
using namespace std;
int f(int n){
    if(n == 0) return 1;
    else return 1 + f(n-1);
}

在上面這個函數中，f 函數自己呼叫了自己！這樣的使用其實是合法的，只要這個呼叫自己的動作會結束就可以。仔細看，每次我呼叫自己的時候，參數 n 都會-1，然後如果 n == 0 會直接 return。這個 n == 0 是所謂的終止條件，他會避免你的遞回一直無窮的跑下去，這個非常重要，每個遞迴都要有終止條件避免無窮遞回。

總結來說，你的函數可以自己呼叫自己。這樣的好處是什麼呢？這個概念就很像我們之前提到的動態規劃，你可以把大問題分成小問題先解決。我們可以呼叫一個遞迴函數，讓他自己遞迴下去跑小問題，跑完的結果再回傳，讓你可以用小問題的資訊解決大問題！

我們用經典的費式數列當例子吧！

給一個 n ，請輸出費氏數列的第 n 項 (1 <= n <= 10000)
費氏數列的定義如下：

  • 第一二項分別是 0, 1
  • 剩下的每一項都是前一項跟前兩項加起來
  • 0, 1, 1, 2, 3, 5, 8 …..

這題有符合我們剛剛提到的，把大問題分成小問題的概念，因為你想算出第 n 項，你需要前一項跟前兩項加起來，很直覺的我們就可以想到遞迴

#include <bits/stdc++.h>
using namespace std;
int f(int n){
    if(n == 1) return 0; // 終止條件 1
    if(n == 2) return 1; // 終止條件 2
    return f(n-1) + f(n-2); // 遞迴算前一項跟前兩項的答案
}
int main(){
    int n;
    cin >> n;
    cout << f(n) << '\n';
}

在WordPress.com寫網誌.