我們昨天在空間複雜度簡單介紹了遞迴，那今天我們來認識他吧 !

遞迴是什麼?

遞迴是函式直接或間接來呼叫自己的過程
簡單來說，就是把大問題拆成小問題，直到問題小到可以解為止
(如下圖)

圖片連結*https://courses.cs.duke.edu/summer02/cps001/Labs/recursion.html

遞迴有兩個重要條件

- 終止條件 (base case)

必須有一個條件讓函式停止呼叫自己
否則會造成 Stack overflow

舉例來說 :

void hello() {
 hello();
}

執行後

hello()
hello()
hello()
hello()
hello()
...

一直重複下去

- 遞迴關係 (Recursive relation)

每次呼叫時，都要把問題拆小

舉例來說 :

 int sum(int n){
     if(n==0) return 0;
     return n+ sum(n-1);
 }

每次 n 都會變小，最後達到終止條件

假設 sum(5)，執行後

sum(5)= 5 + sum(4)
      = 5 + (4 + sum(3) )
      = 5 + (4 + (3 + sum(2) ) )
      = 5 + (4 + (3 + (2 + sum(1) ) ) )
      = 5 + (4 + (3 + (2 + (1 + sum(0) ) ) ) )
      = 5 + (4 + (3 + (2 + (1+0) ) ) )

呼叫堆疊 (Call stack)

當函式被呼叫時，系統都會把資訊存到堆疊中
例如 :

sum(5)

sum(5)
sum(4)
sum(3)
sum(2)
sum(1)
sum(0)

可以想像成

你可能會好奇 :「為什麼sum(0)在最上層」

這就跟我們之前提到的 後進先出(LIFO, Last In First Out)的概念一樣 !
Stack 就是 LIFO 喔!

所以我們來看他是怎麼呼叫的 :

第一步:

sum(5)

stack:

第二步:
計算sum(5)

5 + sum(4)

會呼叫 sum(4)

第三步:

4 + sum(3)

那要呼叫 sum(3)

以此類推，每呼叫一個新的函式，就放在最上面

那接下來開始回傳

n==0 達成 base case

if(n==0){
    return 0;
}

所以 sum(0)這時會彈出(pop)
剩下

接下來

sum(1)
=1+0
=0

完成後一律彈出

以此類推
直到

sum(5)
=5+10
=15

所以也能理解成

一路往下呼叫（Push）
↓
到達 Base Case
↓
一路往上回傳（Pop）

結論就是

遞迴（Recursion）就是函式在執行中呼叫自己，透過不斷縮小問題規模，直到達到終止條件，再逐層回傳結果的技巧。

掌握遞迴最重要的是理解：

「大問題 = 較小的同類問題 + 終止條件」

參考資料

1. https://zh.wikipedia.org/zh-tw/%E9%80%92%E5%BD%92