一、Recursion
1.1 基本觀念介紹
遞迴就是在函式之中呼叫函式自己本身，本質上是將複雜的問題，拆分成具有相同性質的子問題，進而解決問題的方法。
一個基本的遞迴函式一定要有：
終止條件 (基本條件)
遞迴條件 (呼叫自己的條件)
如果沒有終止條件，就會無限循環直到當掉。
範例 1 : 假設輸入一個正整數 n，求 1 + 2 + … + n 的總和
我們可以很直覺的使用迭代 (迴圈) 的方式，將所有數字累加在一起。
但因為這個問題能拆成有規律的數個小問題，
如輸入正整數 2 → 1 + 2 = 3
輸入正整數 3 → 1 + 2 + 3 = 6
…
所以這時候就可以使用遞迴來計算。
Time complexity 是 O(n)，Space complexity 是 O(1)。