owned this note
owned this note
Published
Linked with GitHub
---
tags: 2021CRC
title: 函式與遞迴
slideOptions:
transition: slide
theme:
---
# 函式與遞迴
## 2021/10/22 電算社第五堂社課
---
## 函式
----
火龍果不會算術，他會把8 * 6 寫成 56 (?
為了避免以後他還是運算錯誤
你可以幫他寫一個可以算出
$f(n)= n^2 + 2n -1$ 的程式嗎:D
----
或許你會這樣寫
```cpp=
#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)$
----
```cpp=
#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;
}
```
----
是不是覺得很麻煩呢，
重複的東西一直寫到，
只是帶入的數字不一樣，
卻要重複寫一次類似的東西，
這時候就可以使用函式了喔。
----
### 名詞解釋
* <font color="#FFF300">引數</font>：函式執行時需要輸入的參數
* <font color="#FFF300">回傳值</font>：函式執行完後回傳給呼叫該函式的地方的值，該值的資料型態會被放在函式名字之前，但**不一定每個函式都要有回傳值**
```cpp=
// type 為回傳值的型態 ， name為函式名稱
type name(type1 name1, type2 name2, ... )
{
//函式會做的事
return a; // 回傳a，同時代表該函式的結束，a的型態為type
}
```
----
回到剛剛的題目
```cpp=
#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;
}
```
----
### 函式的功能
當你有某個程式會重複使用到時，
使用函式可以讓你的程式碼更簡潔。
或是當你想把一個功能拉出主程式時會用到！
---
## 寫法範例
輸入a,b
回傳a,b乘積
```cpp=
int func(int n , int m)
{
// n1,m1為我在呼叫這個函式的時候，它的值分別為a , b
// 中間用 , 隔開
return n * m;
}
int main()
{
int a , b;
cin >> a << b;
cout << f(a , b);
}
```
----
void：不回傳
```cpp=
void func(int n)
{
cout << n;
return; //終止函式 （可以省略）
// void代表return後面沒有回傳值
}
int main()
{
int a;
cin >> a;
func(a);
}
```
----
main也是函式
```cpp=
int main()
{
// main本身也是函式，但它前面常用int
return 0; //可以省略
}
```
----
在函式裡面作運算不會影響到函式外的數值，
儘管函式內的東西和main裡面有相同名稱。
```cpp=
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並改值
或把變數開成全域變數
```cpp=
int plus(int a)
{
a += 2;
cout << a;
return a;
}
int main()
{
int a;
cin >> a;
a = plus(a);
cout << a;
}
```
---
## 遞迴
遞迴就是重複執行的函數
有兩個部份：
1. 結束╱繼續的條件
2. 函數本身的執行內容
----
你知道費波納契數列嗎?
就是那個生一堆:rabbit:的故事
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$ 我們就<font color="#fff300">一直利用</font> $a_n = a_{n-1} + a_{n-2}$
----
實作出來長這樣
```cpp=
#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
```
---
之後你會遇到一些一樣需要遞迴的東西
例如 Bottom_Up, Top_Down
----
求費氏數列第i項，可以用迴圈或者是函式做遞迴。
以函式寫法稱為top_down，
以迴圈寫法稱為bottom_up。
ex 輸入：6╱輸出：8
----
```cpp=
//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;
}
```
----
```cpp=
//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
----
```cpp=
// 非遞迴版
#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;
}
```
----
```cpp=
#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;
}
```
---
### OJ練習
[GreenJudge : b022 費氏數列](http://www.tcgs.tc.edu.tw:1218/ShowProblem?problemid=b022)
[ZeroJudge : a044 空間切割](https://zerojudge.tw/ShowProblem?problemid=a044)
[ZeroJudge : e357 遞迴函數練習](https://zerojudge.tw/ShowProblem?problemid=e357)
Google Drive
Gist
Clipboard
Sign in with Wallet
