Fibonacci sequence
The number sequence 0, 1, 1, 2, 3, 5, 8, and so on, where each number is the sum of the two before it.
In more detail
Its textbook recursive definition is the classic example of repeated work: computing the fortieth number naively makes hundreds of millions of calls. Caching results with memoisation, or filling a table bottom-up, brings the cost down to linear time. The course uses it to show both recursion limits and dynamic programming.
Related terms
- recursion — A technique where a function solves a problem by calling itself on a smaller version of the same problem.
- memoisation — Caching a function's results by its arguments so that repeated calls return the stored answer instead of recomputing it.
- overlapping subproblems — The property that a recursive solution solves the same subproblems again and again.
- exponential time — Work that roughly doubles each time the input grows by one, written O(2^n), which becomes impossible to finish for even modest inputs.
Taught in
- Space, In-Place Work And The Call Stack — Algorithms & Data Structures for Working Engineers
- Dynamic Programming: Memoisation And Tabulation — Algorithms & Data Structures for Working Engineers