---
tags: 語法
title: 函式&遞迴
---

:::success
# 函式 Function

## 宣告

### 回傳類別

// "dataType" "nameOfFunction"();
int func();
char func();
long long func();
float func();
bool func();
void func();

int* func();

- 在宣告時告知編譯器函式回傳值的資料類別
- 相當於在回傳前呼叫"dataType"()
- void : 無回傳值

### 形參 Parameter

//"dataType" "nameOfFunction"("dataType" "nameOfVariable");
int func(int num, bool vis);
bool func(int cnt = 0);
    
void init();

- 在宣告時告知編譯器呼叫函式時需要傳入的實參資料類別，並在呼叫時宣告一個屬於此函式的區域性變數來接收實參的值
- 可以先給定默認值，若呼叫時未傳入實參，則照順序套用默認值
- 小括號內為空則表示無需傳入實參
- 在上面的code中為"num"，"vis"，"cnt"等

## 程式定義

int add(int a, int b) {
    return a+b;
} 

- 若回傳型別不為void，至少要有一個return語句
- 可以呼叫全域變數或其他函式

## 呼叫

#include <cstdio>
using namespace std;
int add(int a, int b) {
        return a+b;
}
int main(void) {
    int math, english, ans;
    scanf("%d %d", &math, &english);
    //
    ans = add(math, english);
    //
    printf("%d\n", ans);
    
    return 0;
}

### 實參 Argument

- 呼叫函式時實際傳入的參數值
- 在上面的code中為"math"和"english"

## 宣告 -> 呼叫 -> 定義

#include <cstdio>
using namespace std;
int add(int a, int b);
int main(void) {
    int math, english, ans;
    scanf("%d %d", &math, &english);
    //
    ans = add(math, english);
    //
    printf("%d\n", ans);
}
int add(int a, int b) {
    return a+b;
}

- 可以先告知編譯器函式的存在，使呼叫合法，再在主函式下補充定義
- 注意和"呼叫"標題下code的不同，前者同時完成了宣告和定義
- 可以在需要某個工具時先宣告，之後再來完善工具的code

## 參照 Reference

void swap(int &a, int &b) {
    int temp;
    temp = a;
    a = b;
    b = temp;
}
int main(void) {
    int p, q;
    scanf("%d %d", &p, &q);
    swap(p, q);
    printf("%d %d\n", p, q);
}

- 直接給予實參一個在此函式中使用的代稱，在函式程式中使用使用代稱會直接對位址修改實參的值
- 上面的code會將p與q的值互換並輸出

:::

:::success
# 遞迴 Recursion

## 定義

- 函式重複呼叫自身直到達到停止條件
- 相信每次遞迴都會得到正確結果 -> 有時比迴圈更直觀、更好理解

## 遞迴求最大公因數和最小公倍數

### 數學原理

- 以輾轉相除法求最大公因數，再由$gcd(a, b)\times lcm(a, b) = a\times b$求最小公倍數
- $\forall x,y\in \mathbb Z,x\ge y, gcd(x, y) = gcd(y, x\%y)$
- 重複直到其中一數為0，另一數即為$gcd(x, y)$

### 實作

- 停止條件：y為0

#include <cstdio>
using namespace std;

void swap(int &a, int &b) {
    int temp;
    temp = a;
    a = b;
    b = temp;
}

int gcd(int x, int y) {
    if (y == 0) return x;
    else return gcd(y, x%y); //顯然x%y < y
}

int main(void) {
    int p, q, gcdAns, lcmAns;
    scanf("%d %d", &p, &q);
    if (p < q) swap(p, q); //保證第一次遞迴時x >= y
    gcdAns = gcd(p, q);
    lcmAns = p*q/gcdAns;
    printf("%d %d\n", gcdAns, lcmAns);
}

:::