一、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)。

Linked list 是一種常見的資料結構，會包含 head 和 tail 的資訊，以 null 來代表 Linked list 的終點，使用 node 來記錄、表示、儲存資料。

單向鏈結串列 (單鏈結串列、線性鏈結串列、普通鏈結串列) 是最基本的鏈結串列，其特點是鏈結串列的鏈結方向是單向的，對鏈結串列的存取要通過從頭部開始，依序往下讀取。

每個 node 則會包含 value 和 next (Pointer，指向下一個 node 的位置) 的資訊。