章節連結
重念一次早該補起來的「資料結構與演算法」。這篇筆記來初步簡介一下 Recursion 遞迴。
課程相關資訊
[連結]：https://hiskio.com/courses/572/lectures/29792
本篇範圍：Chapter 4
請注意：本系列文章為個人對應課程的消化吸收後，所整理出來的內容。換言之，並不一定會包含全部的課程內容，也有可能會添加其他資源來說明。
內容
Recursion 遞迴
1. 自己呼叫自己
2. 運用 Stack 的資料結構，後進先出。大量時會造成 Stack Overflow
3. 一定會有一個起始條件 a.k.a. 終止條件
4. 由於 Recursive 會累積 Stack，且會計算重複的內容，因此是可以考慮簡化的方式的。
fibonacciSequence
1. 若用 Recursion，時間複雜度會是 O(n^2)
2. 若用 bottom-up 的方法，將曾經計算過的各個結果存在 array 中方便取用，那就可以降低時間複雜度成 O(n)
