ALGORITHMSChapter 10 · Algorithms and Problem Solving

Recursion

A recursive function calls itself on a smaller piece of the problem. Every recursive function needs a base case that stops the calls and a recursive case that moves toward it. Each call waits for the smaller call to finish and then builds its own answer from the result. Recursion shines on problems that are nested by nature, like folders inside folders.

Worked example

How it reads

Base case: n <= 1 returns an answer without recursing
Recursive case: factorial(n - 1) is a smaller version of the same problem
total_size handles lists nested to any depth by recursing into each child

Common mistakes

Forgetting the base case gives RecursionError: maximum recursion depth exceeded.
Calling with the same size (f(n) instead of f(n - 1)) never reaches the base case.

Cloud tip: Trust the recursion: assume the smaller call already works, and only think about how to use its answer.