Recursion — the Basics
EasyBase case + a smaller subproblem
Recursion is when a function calls itself on a smaller piece — like opening a box that has a smaller box inside, until the tiniest one is easy.
The idea
A recursive function solves a problem by calling itself on a smaller input, stopping at a base case. Trust that the recursive call is correct for the smaller case, and combine its result.
4
3
2
1
0
0
1
2
3
4
Step 1 of 11. factorial(4) calls smaller versions of itself until the base case. Values: 4, 3, 2, 1, 0.
1/11
Optimal
timevariesspaceO(depth)
Base case, then recurse.
1function f(n) {2 if (n === 0) return base; // base case3 return combine(n, f(n - 1)); // smaller subproblem4}Input
- array
- [4, 3, 2, 1, 0]
Memory
- depth
- —
Output
- value
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- fact(4)
- Output:
- 24
- Explanation:
- fact(4) waits on fact(3), which waits on fact(2), then fact(1), then fact(0) = 1. The stack unwinds multiplying back up: 1, 1, 2, 6, 24.
Example 2
- Input:
- sum(3) where sum(n) = n + sum(n-1), sum(0) = 0
- Output:
- 6
- Explanation:
- 3 + (2 + (1 + 0)). You only write the base case and one smaller call; the call stack does the rest.
Finished the walkthrough? Add it to your streak.