[筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 7

重念一次早該補起來的「資料結構與演算法」。這篇筆記來初步簡介一下 Recursion 遞迴。

notes-theideaofalgorithm-javascript-1


課程相關資訊

[連結]: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)


程式碼

https://github.com/andy922200/hiskio-the-idea-of-algorithm/commit/9f32e937dd25b4989613b9b9a6e86ec7a32d0ac3


系列文章

  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 9
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 8
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 6
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 5
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 4
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 3
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 2
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 15
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 14
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 13
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 12
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 11
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 10
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 1
  • 按讚加入粉絲團

    延伸閱讀