8.Algorithms: Recursion 學習筆記
Published in
Jul 17, 2021
學習資料來源: Master the Coding Interview: Data Structures + Algorithms
【Algorithms: Recursion】
在函式中呼叫函式本身,範例
優點: 簡潔易讀
缺點: 占用記憶體(Large Stack),容易造成stack overflows
特性:
- 常用於處理Divide and Conquer狀況,如:Merge Sort, Quick Sort, Tree Traversal, Graph Traversal
- 可以用Recursion的也能用Iterate(loop)處理
- 須設定終止的條件,否則會產生無窮迴圈
練習 :【Recursion factorial】
ex: findFactorialRecursive(5) => 5!=5**4*3*2*1 => should return 120
練習 :【Recursion fibonacci】
Given a number N return the index value of the Fibonacci sequence, where the sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 …
the pattern of the sequence is that each value is the sum of the 2 previous values, that means that for n=5 => 2+3
ex: fibonacciRecursive(6) => 3+5 => should return 8
回到筆記列表,文章中的內容如果有誤,歡迎提醒告知,謝謝!