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

Taught in

References