函式與遞迴

火龍果不會算術，他會把8 * 6 寫成 56 (?
為了避免以後他還是運算錯誤
你可以幫他寫一個可以算出
\(f(n)= n^2 + 2n -1\) 的程式嗎:D

或許你會這樣寫

#include<iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    cout << n * n + 2 * n - 1;
    return 0;
}

但當你需要使用很多次怎麼辦呢

例如我想要知道輸入兩個數字\(n_1, n_2\)
然後算出\(f(n_1) - f(n_2)\)

#include<iostream>
using namespace std;
int main(){
    int n1, n2;
    cin >> n1 >> n2;
    cout << (n1 * n1 + 2 * n1 - 1) - (n2 * n2 + 2 * n2 - 1);
    return 0;
}

是不是覺得很麻煩呢，
重複的東西一直寫到，
只是帶入的數字不一樣，
卻要重複寫一次類似的東西，
這時候就可以使用函式了喔。

名詞解釋

• 引數：函式執行時需要輸入的參數
• 回傳值：函式執行完後回傳給呼叫該函式的地方的值，該值的資料型態會被放在函式名字之前，但不一定每個函式都要有回傳值

// type 為回傳值的型態 ， name為函式名稱
type name(type1 name1, type2 name2, ... )
{
    //函式會做的事
    return a; // 回傳a，同時代表該函式的結束，a的型態為type
}

回到剛剛的題目

#include<iostream>
using namespace std;
int f(int n){
    return n * n + 2 * n - 1;
}
int main(){
    int n1, n2;
    cin >> n1 >> n2;
    cout << f(n1) - f(n2);
    return 0;
}

函式的功能

當你有某個程式會重複使用到時，
使用函式可以讓你的程式碼更簡潔。
或是當你想把一個功能拉出主程式時會用到！

void：不回傳

void func(int n)
{
    cout << n; 
    return; //終止函式 （可以省略）
    // void代表return後面沒有回傳值
}
 
int main()
{
    int a;
    cin >> a;
    func(a);    
}

main也是函式

int main()
{
    // main本身也是函式，但它前面常用int
    return 0; //可以省略
    
}

在函式裡面作運算不會影響到函式外的數值，
儘管函式內的東西和main裡面有相同名稱。

void plus(int a)
{
    a += 2;   
    cout << a << " ";
}
int main()
{
    int a;
    cin >> a;
    cout << plus(a);
}
/* 
輸入2 ， 輸出4 2
因為plus(a) 裡面的a只是把數值複製到函式
所以a再函式作加減乘除，不會對main裡面的a有所影響
如果要改變a，要把a return
並把main的a 改為plus(a)
*/

如果要作改變
要return並改值
或把變數開成全域變數

int plus(int a)
{
    a += 2;
    cout << a;
    return a;
}
 
int main()
{
   int a;
   cin >> a;
   a = plus(a);
   cout << a;
}

你知道費波納契數列嗎?
就是那個生一堆的故事
1, 1, 2, 3, 5, 8, … \(a_{n-2}\), \(a_{n-1}\), \(a_n\)
你會得到一個關係式：\(a_n = a_{n-1} + a_{n-2}\)

你未來一定會遇到一個時候
會有人要你寫出
算費式數列第 \(n\) 項的Code(像現在:D)

那你要怎麼寫哩?

邏輯：我們知道第一項跟第二項是1
如果 \(n\) 為 \(1\) 或 \(2\) ，就回傳 \(1\)
其他的 \(n\) 我們就一直利用 \(a_n = a_{n-1} + a_{n-2}\)

實作出來長這樣

#include<iostream>
using namespace std;
 
int Fibonacci(int n){ //n是要求第n項的意思
    if(n == 1 || n == 2){
        return 1;
    }
    else{
        return Fibonacci(n-1) + Fibonacci(n-2);
    }
}
 
int main(){
    int n;
    cin >> n;
    cout << Fibonacci(n) << endl; 
    return 0;
}
//輸入：6
//輸出：8

求費氏數列第i項，可以用迴圈或者是函式做遞迴。
以函式寫法稱為top_down，
以迴圈寫法稱為bottom_up。

ex 輸入：6╱輸出：8

//top_down
#include<iostream>
using namespace std;
 
int f(int n)//n是要求第n項的意思
{ 
    if(n == 1 || n == 2) return 1;
    else return f(n-1) + f(n-2);
}
 
int main()
{
    int n;
    cin >> n;
    cout << f(n) << endl; 
}

//botton_up
#include<iostream>
using namespace std;
 
int main(){
    int n;
    cin >> n;
 
    int f[n + 1]; //多一項，讓項數變成1 ~ n，較直觀
    f[1] = f[2] = 1;
 
    for(int i = 3; i <= n; i++){
        f[i] = (f[i ‐ 1] + f[i ‐ 2]);
    }
    cout << f[n];
}

試試用函式和遞迴做做 3n+1 吧
當某一個數是奇數，就對他乘以三再加一
如果是偶數，就對他除以二
如此循環，最終都能得到1
試著輸出進行的過程吧

輸入說明：輸入一個整數\(n\)
輸出說明：輸出\(3n+1\)進行的過程，每個數字用一個空格隔開
範例輸入：5
範例輸出：5 16 8 4 2 1

我是防雷頁:D

// 非遞迴版
#include<iostream>
void N(int n){
    while(n != 1){
        if(n % 2 == 0){
            n /= 2;
            cout << n << endl;
        }
        else{
            n = 3 * n + 1;
            cout << n << endl;
        }
    }
    cout << n;
    return;
}
 
int main()
{
    int n;
    cin >> n;
    N(n);
    return 0;
}

#include<iostream>
using namespace std;
void N(int n){
    cout << n << ' ';
    if(n == 1){
        return;
    }
    else{
        if(n % 2 == 0){
            N(n/2);
        }
        else{
            N(3 * n + 1);
        }
    }
    return;
}
int main(){
    int a;
    cin >> a;
    N(a);
    return 0;
}