# 基本觀念 遞迴同數學的遞迴，都需要找到關係式，並且每個在範圍內的正整數都必須要對應一個值。 以費式數列為例，一個費式數列如下 $[1,1,2,3,5,8,……,F(n-1)+F(n-2)]$ 我們可以定義一個關係式 $$ F[n]=\begin{cases} F[0]=F[1]=1 \\[2ex] F[n]=F[n-1]+F[n-2] \end{cases} $$ # 用法 ## 範例程式碼 ```cpp= #include <bits/stdc++.h> using namespace std; int h; int f(int x) { if(x>10) return x; else return f(x+1); } void d(int x,int y) { if(x>y) { h++; return; } return; } void g() { if(h>0) { h--; return; } return; } int main() { int a=10,b=50,c=10; h=0; cout<<f(a)<<endl; d(b,a); cout<<h<<endl; g(); cout<<h<<endl; return 0; } ``` ## 解析 ### f 以第4行為例 ```cpp= int f(int x) ``` :::info 前面的 **"int"** 表示 **"回傳"** 東西的型態 中間的 **"f"** 表示這個函式稱為 **"f"** 後面的 **"int x"** 表示這個函式需要 **"輸入"** 的一個值 ::: 4到10行可以視為是一整個區塊 ```cpp= int f(int x) { if(x>10) return x; else return f(x+1); } ``` 整個區塊的流程為 :::warning $1. 輸入一個x$ $2. 如果x大於10 回傳x$ $3. 否則x+1直到x>10$ ::: ### d ```cpp= void d(int x,int y) { if(x>y) { h++; return; } return; } ``` 以這個區塊來看 :::success **型態=>void 名字=>d 輸入=>x,y** ::: 這裡有兩個重點 :::info **void** ``` void(N.) 空洞；空間；空白(From Cambridge) ``` 而這裡void便是表示回傳值為空，也就是**沒有**回傳值。 ::: :::info **兩個輸入值** 對，兩個輸入就是得這樣，沒有為什麼。 ::: ### g ```cpp= void g() { if(h>0) { h--; return; } return; } ``` 以這個區塊來看 :::success **型態=>void 名字=>g 輸入=>???** ::: 事實上，這裡**不須要**任何輸入，直接呼叫即可。 ### 變數 首先，每個區塊裡的變數都**不會**共用，所以f裡面的x跟d裡面的x是**不同的**x。 假使你需要一個每個區塊都可以使用的變數，在這個程式中就是h，你只需要宣告在所有程式碼區塊前即可。 ## 流程 首先，程式碼必然是先從main開始，**一個程式只能有一個main**，這是規則，~~不能打破(梗)~~。 ```cpp= int main() { int a=10,b=50,c=10; h=0; cout<<f(a)<<endl; d(b,a); cout<<h<<endl; g(); cout<<h<<endl; return 0; } ``` 假如是有回傳值的函數，例如f，可以指定給變數或是直接輸出，假如是無回傳值的函數，例如d,g，則**不可**指定給變數或是直接輸出，因為沒有回傳值。 (呼叫方法即為程式碼內容) # 總結 遞迴在使用時複雜度是呈現指數型上升的，在未來，我們會利用動態規劃來優化這部分的複雜度，費式數列或階層的運算會有更好的解法。