Recursion and the call stack
A recursive function is easy to write and hard to picture. These five run on input you choose and record every call they make, so you can watch the stack pile up, watch each value hand back down it, and count what the whole thing cost.
5 algorithms
- FactorialMultiplies n by the factorial of n − 1, all the way down to the base case. The simplest possible recursion: one call in, one call out, no branching.O(n)O(n) spaceup to n = 20
- Fibonacci, naiveComputes fib(n) as fib(n − 1) plus fib(n − 2), recomputing every shared subproblem from scratch. The calls counter makes the waste countable rather than asserted.O(2ⁿ)O(n) spaceup to n = 16
- Fibonacci, memoisedThe identical recursion as naive Fibonacci, with one change: remember every answer once it is known, and read it back rather than recomputing it.O(n)O(n) spaceup to n = 25
- Towers of HanoiMoves a stack of discs from one peg to another using a third as a spare, moving n − 1 discs out of the way before the largest can move, then back again afterwards. Recursion that works on the way down and the way up.O(2ⁿ)O(n) spaceup to n = 8
- PermutationsBuilds every arrangement of a small set of values by choosing one at a time, then undoing that choice once every arrangement it could lead to has been found. The undo step is backtracking's defining move.O(k!)O(k) spaceup to n = 5
Nothing matches that. Clear the filter to see all 5.
Sorting and searching live next door in AlgoLab.