Where it runs
1. The problem
In the last group of lessons you built a stack yourself: a pile you put work onto and take it off. Recursion (a function calling itself) gives you the same kind of stack, only the language keeps it. Every time a function calls itself, the runtime puts the unfinished work on the stack. Every time a function returns, the runtime takes it off. You use a stack without managing it by hand, and for this problem that is very convenient.
You want the total size of a folder. If it holds 4 files, it is simple: read the size of each and add them up. But the folder holds folders, those hold more folders, and you don't know how deep it goes until you look.
Plain loops can't handle this. To write nested loops, you need to know the shape of the data in advance. Here the shape is: unknown depth, and any number of branches at every level. You can't nest for inside for five times and hope five levels are enough.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedrecurse(4)recurse(n) adds n + (n - 1) + ... + 0. Each call does one step and hands a smaller n to the next call. Start with recurse(4).
Recognise it
Say these words and it is this pattern
- problem is defined in terms of a smaller version of itself
- nested/tree-shaped structure to walk (directory, expression, linked list)
- compute a count/sum/depth over all sub-elements
- natural base case + recursive case split (factorial, Fibonacci, tree depth)
Looks similar, isn't
- Recursion with memoization
Memoisation is this plus a cache of past answers. Add it once the same argument comes back.
- Backtracking
Backtracking undoes a choice after exploring it. Plain recursion never undoes anything.
- Stack (LIFO)
The call stack is a stack you did not write. Writing your own removes the depth limit.
- Tree traversal
Trees are where recursion is cheapest and clearest. That page is about the three visit orders.
Depth up to roughly 10000 is safe in a browser. Deeper than that, rewrite the recursion as a loop.
On LeetCode
Problems where the answer for the whole is built from answers for smaller pieces of the same shape, such as nested lists or reporting chains. Write the base case, then call the function on each piece and combine.
The textbook recursion with two base cases, and n stays at 30 or less, so the plain version passes.
The lesson's manager example, where an employee's total is their own importance plus the totals of their direct reports.
Halve the exponent on each call and square the result, so the depth is log n instead of n.
Flatten the nested list recursively in the constructor, the same walk as listing files inside folders.