Recursion的概念就是把大問題化成小問題，最後在去解決小問題，解答會由小問題組成。
那要如何去把大問題拆成小問題呢?
我們可以先思考小問題是什麼?為什麼要有小問題?
- 大問題通常很難直接解決，但是如果把問題分解成小問題，就可以讓問題變得更容易處理。
- 小問題的解決方法通常比較簡單和直接，因此可以幫助我們理解和解決原問題。
例如，如果計算一個長度為n的數列的總和。這個問題可以分解成計算前n-1個元素的總和，再加上第n個元素的值。這樣，原本的大問題就就可以分為為兩個小問題：1. 計算前n-1個元素的總和，2. 計算第n個元素的值。這兩個子問題可以遞迴地解決，最後得到大問題的解答。
在這個例子中，小問題是計算一個元素的值，大問題是算整個數列的總和。通過分解成小問題，我們可以更容易地理解和解決原問題。
以Tree來說，左子樹和右子樹的結果是小問題的答案，我們沒有辦法在root這個點就知道下面的問題，但每個node都會期待小問題會給我解答，所以一直不停把問題丟下去拆成小問題，結果會從result傳回來，拿回傳值做判斷。
Bottom-up 和 Top-down
在前幾個tree章節，我們也用過Recursion的解法，Recursion又分成Bottom-up 和 Top-down 方法，而Top-down 或Bottom-up 內又有許多解法，例如 Top-down 方法內又分成Backtracking 回溯或是其他解法。這裡就先以Top-down 和Bottom-up 為中心來說明。
- Bottom-up
Bottom-up 方法通常要先思考leaf 終止條件，從子問題開始，預期左右子樹兩邊會傳回什麼，思考怎樣形成root的答案，最後再去防一下是空的怎辦?沒有左邊或右邊怎麼辦?就這樣一步步去構建解決方案，直到求解大問題的最優解。每個子問題的最優解都被計算一次，並存儲在一個表格或數組中。最後，這些子問題的解決方案被組合成一個整體解決方案，解決大問題的最優解。
Bottom-up 方法的keypoints是
- 要先思考leaf 終止條件
- 要去思考如何把變數由leaf往上帶到root
- 如何處理每個節點，考慮每個節點的特點，並且適當地處理各種可能的情況(是空的怎辦?沒有左邊或右邊怎麼辦?)
以下為Bottom-up 的一個例子
509. Fibonacci Number
- Top-down
Top-down 方法則是從大問題開始，遞歸地解決其子問題，直到求解最小的子問題為止。這種方法比較像正常人的思考方式，但CODE會比較常比較醜，目前執行的行數和變數會存在MemoryStack， 所以空間複雜會使O(d) ，d是樹的深度，而時間複雜會是O(n)，n 是樹的節點數。
Top-down 方法的keypoints是
- 要去思考如何把變數由根往下帶
- 用global variable把變數存起來
- 如何處理每個節點，考慮每個節點的特點，並且適當地處理各種可能的情況(是空的怎辦?沒有左邊或右邊怎麼辦?)
以下為Top-down 的一個例子
Top-down 的Recursion：計算n的階乘
def factorialTopDown(n: int) -> int:
dict = {} # 使用字典記錄已經計算過的n的階乘值
def recr(n):
if n in dict:
return dict[n]
if n == 1:
dict[n] = 1 # 1的階乘為1
else:
dict[n] = n * recr(n - 1) # 計算n的階乘
return dict[n]
return recr(n)
112. Path Sum
Bottom-up 和 Top-down 哪個比較好呢?
Bottom-up會比Top-down 來的好，因為有方法加速且不需要使用 Memoize 技術的情況下，就已經可以有效地避免重複計算。
Tail recursion
Tail recursion是一種特殊的遞歸形式，它在函數的最後一步(最後一行)才有tail recursion，且一定是bottom-up方法，關於空間複雜度，只有在C/C++會幫你優化成O(1)
509. Fibonacci Number
Pass by reference & pass by value
參考文章 : Python 是 Pass By Value, Pass by Reference, 還是 Pass by Sharing？
Pass by reference（按參考傳遞）和 pass by value（按值傳遞）是兩種不同的參數傳遞方式。
Pass by value 指的是將參數的值複製一份，然後將這份複製的value傳遞給函數。在函數內部對參數進行修改不會影響原來的value。這種方式適用於immutable(不可變類型)的參數，例如 int、float、str 等。因為這些類型的value不可被修改，所以比較不會出現問題。
Pass by reference 指的將參數的引用（內存地址）傳遞給函數。在函數內部對參數進行修改會影響原來的值。這種方式適用於mutable(可變類型)的參數，例如 list、dict、set、tuple 等。這些類型的值可以被修改，所以可能會出現問題。