一、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)。
範例 2 : 階層運算，假設給一個正整數 n，n! = (n - 1) * (n - 2) …* 3 * 2 * 1
Time complexity 是 O(n)，Space complexity 是 O(1)。
範例 3 : Fibonacci 費波那契數列 (費氏數列)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
給予 n，請求 f(n)。
每個數字都是前兩個的總和
第 0 項 f(0) = 0
第 1 項 f(1) = 1
第 3 項 f(2) + f(1) = 2
第 n 項 f(n) = f(n - 1) + f(n - 2)
但這裡的 Time complexity 是 O(2^n)，Space complexity 是 O(n)。
因為假設求 fibonacci (5)，會看到有不斷被重複運算的值如 f(0), f(1), f(2) 等等；
為了降低 Time complexity 可以建立一個 cache 去存已經計算過的值。
(https://www.wongwonggoods.com/school-notes/algorithm/dynamic-programming/)
這樣 Time complexity 就會是 O(n)，Space complexity 是 O(n)。
1.2 遞迴和迭代(迴圈)比較
遞迴
呼叫 stack 是有大小限制的，當過多的函式呼叫導致無法容納這些呼叫的位址，就會發生堆疊溢位 (stack overflow)
遞迴執行效率較迴圈慢，因為需要進行函式呼叫
迭代(迴圈)
迭代(迴圈) 的程式碼較遞迴來的冗長
1.3 實際運用範例
只要是大問題可以拆解成小問題的狀況都可以用 recursion，
在 binary tree 蠻常用到 recursion。
二、題目整理
之前的參考文章沒有蒐集常出現之 recursion 的問題，因為常和 binary tree 一起考，
沒有留言:
張貼留言