# 函式
## 一、 介紹
Function 是建構程式的一個小區塊，可以自己決定它有何功能，以及所需要的參數 (input) 和輸出 (output)。
你可以把 function 比做數學上的公式 (formula)，一樣有參數跟結果，「輸入」參數給公式，透過公式「運算」出「結果」。
函式可以想像成是鋼彈中的小零件，各個小零件有不同的功能，透過這些零件 (function) 組成一個完整的鋼彈 (program)。
## 二、優點
#### 程式的重複利用性：
如果我們想要重複地做一件事，將這個功能寫成 function 會較為容易使用，需要時再進行呼叫，不必擔心會不會在複製貼上時出了什麼差錯等等導致程式碼變成一團混亂，且能讓主程式乾淨簡潔。
#### 程式的易讀性：
將功能包裝成一個名稱明確的函式，能夠使其他人在閱讀你的程式碼時，更能理解這一個區段所要進行的操作是什麼，增加易讀性。
#### 程式的易除錯性：
寫成函式的好處還有較容易 debug 找出其中的錯誤，當發現程式所跑出的結果不如預期時，只需要檢查定義函式時有無差錯即可，不需要在使用同一個功能的每個段落都檢查一次是否有邏輯上的問題，或是不小心更動了程式碼的內容。
#### 程式的一致性：
當程式的學習到了後來，與其他人一同撰寫一個大型專案是很常遇到的事情，此時如果你將你所寫的這一個功能包裝成一個 function 再傳給別人繼續作業時，就比較不會更動到這個函式當中的內容，後續進行維護也較為容易。
#### 程式的模組化：
模組化是一個在撰寫程式時的概念，如果將寫一個完整的程式視為組鋼彈，那麼函式就像是鋼彈的零件，每個零件都有著不疼的功能。程式是由許多個函式以及其他東西所建構出來的，而且函式與函式之間的分工十分明確，每一個函式有它自己所負責的東西，並且可以獨立於這個程式來看。
## 三、 函式基本形式
```python=1
def 函數名稱(參數)：
函數內容
return 回傳值
```
一個函式必定擁有下面四個東西
1. **函式名稱**：可任意取，盡量跟函式功能有關
2. **參數**：可指定任意參數 (input)
3. **函數內容**：函式的運算處理過程 (process)
4. **回傳值**：函式運算完的結果將其回傳 (return)，預設回傳值為空(None)
## 四、示範程式
### 1. 函式：無參數
單純將函式內的程式碼跑過一輪。
> 範例
```python=
def hello():
print("hello world.")
hello()
```
> 輸出
```
hello world.
```
乍看之下是要印出hello world但實際上的回傳值是沒有東西的，將其印出來會發現…變數為None!!!
> 範例
```python=
def hello():
print("hello world.")
a = hello()
print(a)
```
> 輸出
```
hello world.
None
```
**程式說明**：
1. 我們先用變數 `a` 來接住函式的回傳值，然後印出 `a`。
2. 編譯器會先跑函式，所以先印出hello world，然後回傳值，但是回傳值為空，所以 `a` 沒有接到任何回傳值因此印出 `None`。
＊如果我們將函數最後加入回傳值(return)
> 範例
```python=
def hello():
print("hello world.")
return "hello"
a = hello()
print(a)
```
> 輸出
```
hello world.
hello
```
我們可以發現此時 `a` 有接到函式的回傳值 `hello` ，並且印出。
以上就是回傳值的功能以及有無return的差異。
### 2. 函式：有參數
> 範例
```python=
def calculate(x, y, op):
if op == '+':
return x+y
if op == '-':
return x-y
if op == '*':
return x*y
if op == '/' and y != 0:
return x/y
else:
return "Wrong"
print(calculate(1, 2, '+'))
print(calculate(1, 2, '-'))
print(calculate(1, 2, '*'))
print(calculate(1, 2, '/'))
print(calculate(1, 2, 'o'))
```
> 輸出
```
3
-1
2
0.5
Wrong
```
**程式說明：**
這是個簡單的計算機，在最一開始我們會傳入3個參數，分別是 x, y, op，a跟b代表要被計算的數字，而op代表者運算符號，經過許多if-else的邏輯判斷後，最後回傳符合要求的答案，這就是一般函數的基本寫法。
## 四、 參數傳遞
1. **全域變數**：此種變數在整個程式的任何地方皆可呼叫
<font color="#f00">[注意]：</font>當區域變數名稱與全域變數名稱相同，區域變數會遮蓋 (Shadow) 全域變數。
2. **區域變數**：只能在函式內使用，不可在函式外呼叫
+ 區域變數只能在其所定義的區域中使用，在該區域以外就無法使用
+ 區域變數的壽命：函式開始執行時開始生命，函式執行完畢就結束
> 範例
```python=
x = 10
def function():
y = 20
y = x + 10
print(y)
function()
print(x)
print(y)
```
> 輸出
由此程式碼我們可以看到有兩個重點：
(1) `x` 的值在函數內被取用，也可以在主程式被列印
(2) `y` 無法在主程式被印出來，並顯示為定義
`x` 就是全域變數而 `y` 就是區域變數，`y` 被定義是一因為他的生命週期就在函式被呼叫到函數就數為止，所以系統才會認定程式未定義。
在撰寫程式會不建議使用global來傳遞參數，因為維護太麻煩了，例如變數名稱更改，所有相關的def都要更改，又或者是會有 local global 名稱重疊（會判給local）等等所以我們會希望透過參數把我們要的資訊傳進去。
### 1. 數字、字串傳遞
> 範例
```python=
def add(x, y, z):
return x+y+z
print(add(1, 2, 3))
```
> 輸出
```
6
```
這是一個簡單的加法函式，將傳進去的數字相加
> 範例
```python=
def Print(word):
word = word + "hello"
print(word)
word = "hi"
Print(word)
print(word)
```
> 輸出
```
hihello
hi
```
注意：把 `word` 傳進去後裡面的 `word` 就是區域變數，這時裡面的 `word` 改變，不會影響到外面的 `word`，所以 `print(word)` 還是維持原本的 `word`。
### 2. 串列、字典傳遞
數字跟字串傳遞不會牽涉到記憶體的，我們稱為傳參，但在做list,dict甚至之後會交到的class 就要用到傳址，也就是傳遞整個list的位置給他
> 範例
```python=
def Eat(order):
while order:
print(f"{order.pop()} 餐點已送出)
order = {"apple", "chicken", "rice", "french fries"}
print("client order: ", order)
Eat(order)
print(order)
```
> 輸出
```
client order: ['apple', 'chicken', 'rice', 'french fries']
french fries 餐點已送出
rice 餐點已送出
chicken 餐點已送出
apple 餐點已送出
[]
```
在把order傳入時，他會把 `Eat` 裡面 `order` 跟外面的 `order` 綁在一起，就像 `order(local) = order(global)` ，因此裡面的 `order` 被修改後外面的 `order` 也理所當然的被更改。
如果不想要更改到原本的值我們會傳遞副本進去，我們可以這樣更改
> 範例
```python=
def Eat(order):
while order:
print(f"{order.pop()} 餐點已送出")
order = {"apple", "chicken", "rice", "french fries"}
print("client order: ", order)
Eat(order[:])
print(order)
```
> 輸出
```
client order: ['apple', 'chicken', 'rice', 'french fries']
french fries 餐點已送出
rice 餐點已送出
chicken 餐點已送出
apple 餐點已送出
['apple', 'chicken', 'rice', 'french fries']
```
# 遞迴
## 一、 介紹
有時我們解決一個問題的方法是將其拆解，再各自將小問題解決以後得到答案，這樣的概念我們稱之為“**Divide and Conquer**”，中文稱為「**分治法**」。
遞迴這個方法就是依據此概念形成的：我們將一個龐大的問題切分成數個相似的中問題，然後將中問題再區分成許多小問題，再將這些小問題用同一個function解決，最終將這個大問題處理完，這個處理方式就稱作**recursion**。
## 二、 形式
在數學以及電腦科學的領域當中，當一個函式會在執行當中，會不斷地自己呼叫自己時，我們便認為這個函式具有遞迴的性質。同時，為了避免函式永無止盡地自我呼叫(self-calling)，我們也需要設計一個明確的「終止條件」。
因此，我們便得到了設計一個遞迴函式的兩個重點：
<font color="#f00">(1) 遞迴自我呼叫的方式</font>
<font color="#f00">(2) 結束呼叫的終止條件</font>
## 三、 基本遞迴函式
### 1. 階乘
階乘問題是我們從高中就學過的數學問題， n 階 n!代表的即是從 1 開始連乘直到 n 為止，意即 n! = 1 x 2 x ... x n。
當我們需要用程式來幫助我們寫出一個計算階乘的函式，大家可能會先想到的是迴圈，在這個函式當中，我們只需要一個 n 次的 for loop 就可以解決這個問題。在函式當中設定一個變數用來記住目前的乘積，然後從 1 開始乘直到 n 為止
==迴圈寫法==
> 範例
```python=
def factorial(n):
factor = 1
for i in range (1, n+1):
factor = factor * i
return factor
print(factorial(5))
```
> 輸出
```
120
```
雖然我們可以用迴圈來解決這個問題，但我們可以嘗試用「遞迴」的概念來重新審視階乘
```
n! = 1 * 2 * 3 * … * n-1 * n
```
若我們把乘上n以前的乘積拿出來看的話…
```
n! = (1 * 2 * 3 * … * n-1) * n = (n-1!) * n
```
會發現想得到n階乘只要先得到n-1階乘在乘上n就好了
以此類推，n-1階來自於n-2階乘上n-1、…、 2階等於1階乘上 2。那麼1階呢？0階呢？這兩者從我們高中所學的數學可以得知，我們將兩者皆定義為1。
到這邊為止是否對於階乘以及遞迴有更深一層的理解了呢？
接下來就來實作吧！
==遞迴寫法==
factorial(n)這個函式的定義如下：參數 n 是 1 或 0 的話，就回傳 1 ；不是的話就 return n 乘上用 n-1 當作參數呼叫自己的回傳值，也就是 factorial(n-1)。
> 範例：
```python=
def factorial(n):
if n == 1:
return n
else:
return n * factorial(n-1)
print(factorial(5))
```
> 輸出
```
120
```
### 2. 費氏數列
費氏數列也是在傳達遞迴概念時，經常被提及的一個問題。
**費波那契數列** : 一個數列，每一項都等於他的前兩項的和，也就是說第 n 項等於第 n-1 項以及第 n-2 項的和。
**數學式**：
```
f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2), n>=2
```
首先，我們想要求得的是第 n 項的值，也就是我們的函式參數為整數 n ，它每一次都會呼叫以 n-1 為參數以及 n-2為參數的函式，並且將他們的回傳值相加起來再 return 。但若參數值為 1 或是 0 ，根據費氏數列的定義，我們就要直接回傳 1 和 0 。
> 範例
```python=
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7))
```
> 輸出
```
13
```
解釋完了遞迴的想法，不妨來思考要如何利用迴圈來解決同樣的問題吧！
==迴圈寫法==
```python=
def fibonacci(n):
if n == 1 or n == 2:
return 1
else:
f1 = 1
f2 = 1
f3 = 0
for i in range (2, n):
fib3 = fib1 + fib2
fib1 = fib2
fib2 = fib3
return fib3
print(fibonacci(7))
```
> 輸出
```
13
```
使用迴圈所寫的程式碼想法依舊不難，只是相較於遞迴的寫法而言，程式碼閱讀起來稍微不那麼直觀一些。
## 四、 遞迴的複雜度問題
在了解遞迴函式的概念以後，不知道大家是否也都有感受到遞迴有著理解上簡單明瞭，又可以縮短程式碼長度的好處。
那麼，為什麼在多數遞迴可以處理的問題當中，大家還是比較常使用迴圈而不是遞迴呢？
我們再複習一下費氏數列的例子
```python=
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(7))
```
我們可以看到，在程式碼當中，這一個函式呼叫了兩次自己。但是與此同時，在進行下一層的計算以前，我們還要先記得等等下一層的函式回傳回來以後，我要將兩個回傳值相加。也就是說，在參數為n時，我們呼叫了fibonacci(n-1)以及fibonacci(n-2)，並且在真的計算fibonacci(n-1)以及fibonacci(n-2)之前，還要先記住這裡要將他們加起來。
很顯然地，在這一個遞迴函式裡，我們在知道要計算fibonacci(n-1) + fibonacci(n-2)時，要等到將fibonacci(n-1)以及fibonacci(n-2)都計算完以後，再回來這裡將兩個回傳值相加起來。但是電腦要怎麼知道等到得到回傳值以後，我們要將它相加呢？那就是因為電腦在看到fibonacci(n-1) + fibonacci(n-2)時就已經記住了等等要相加，才開始計算fibonacci(n-1) 以及 fibonacci(n-2)。而這個“記住”的動作當然會花電腦的記憶體，等到函式得到回傳值以後再從記憶體當中拿出來。也就是說，電腦在一層一層從參數為n 、n-1、…一直計算到fibonacci(1)以前，需要記住n這麼多個加，除此之外，在其他的遞迴問題當中可能還會需要記住其他數字等，總之需要將每一層的數值、操作等等都存在電腦暫時的記憶體當中。
除了遞迴本身需要記住每一層的資訊以外，有時我們還可能讓電腦做重複的事情。同樣使用剛才費氏數列的例子，我們在計算第 n 項的值時需要計算第n-1項以及第n-2項的數值，而第n-1項的值又來自於n-2以及n-3項，第n-2項的計算又要用到第n-3項以及第n-4項…
然而，電腦並沒有聰明到記得你剛才想要計算 f(n)的時候已經呼叫過f(n-2)了，在你呼叫f(n-1)時又會呼叫f(n-2)一次，因此光是f(n-2)這個函式就執行了兩次。而f(n-3)更是在計算f(n-1)時被呼叫一次，然後在計算兩次f(n-2)時又被各自呼叫一次…更別提最後的f(1)、f(0)會被呼叫多少次了！
而且這些函式所回傳的值也通通都會被存在記憶體裡直到同一層的函式都被執行完為止，因此佔用了大量的空間，而且經常會把曾經做過的事情又拿來重新做一遍，不只「浪費時間」，「也浪費空間」，造成了程式的不效率(inefficiency)。
用電腦科學的話來講，就是遞迴這樣的方法會增加時間複雜度(time complexity)：在這個費氏數列的例子底下，使用迴圈解時，隨著我們輸入的n變大m倍，也只是迴圈多跑m倍的次數而已，也就是說時間的增加是線性的(linear-time)；但是在遞迴解的情況底下，m倍的n所增加的時間可不只是m倍而已，而是指數增加(exponential-time)。於此同時，遞迴的使用也會使函式為了記住之前的結果而多耗費更多記憶體，進而增加空間複雜度(space complexity)。
參考資料：
https://medium.com/ccclub/ccclub-python-for-beginners-tutorial-244862d98c18
Sign in with Wallet
Connect another wallet