Recursion

You want to know how many files are in your Photos folder. Inside it are some photos, but also folders: "2023", "2024", "Holidays". Inside "Holidays" are more folders, one per trip. Inside those, maybe more. You do not know how deep it goes.

A plain loop struggles here, because you would need one loop per level and you do not know how many levels there are. But there is a very natural way to describe the job: "The number of files in a folder is the files directly in it, plus the number of files in each of its subfolders." That sentence uses the job to describe itself. That is recursion.

#The idea: solve a smaller copy

A recursive function is a function that calls itself on a smaller piece of the problem. Every recursive function has two parts:

• Base case. A piece so small you can answer it directly, without calling yourself. For the folders: a single file counts as 1.
• Recursive case. Break the problem into smaller pieces, call yourself on each, and combine the answers. For the folders: add up the counts of everything inside.

The base case is what stops the calls. Each recursive call must move closer to it. A subfolder always has fewer things inside than the folder around it, so the calls keep shrinking until they hit single files.

Here a folder is a list, and each item in it is either a file (a string) or another folder (a list). The Photos example might look like ["a", ["b", "c"], "d"]: two files at the top, plus a subfolder holding two more.

function countFiles(item) {
  if (typeof item === "string") return 1; // base case: one file
  let total = 0;                          // recursive case: a folder
  for (const child of item) {
    total += countFiles(child);           // trust the smaller call
  }
  return total;
}
 
countFiles(["a", ["b", "c"], "d"]);                 // 4
countFiles(["a.jpg", ["b.jpg", ["c.jpg", []]], []]); // 3

def count_files(item):
    if isinstance(item, str):
        return 1  # base case: one file
    total = 0     # recursive case: a folder
    for child in item:
        total += count_files(child)  # trust the smaller call
    return total
 
count_files(["a", ["b", "c"], "d"])                  # 4
count_files(["a.jpg", ["b.jpg", ["c.jpg", []]], []])  # 3

Look at how little the function does. It never tries to handle grandchildren or great-grandchildren. It only says "ask each child for its count and add them up". Any depth works, including empty folders: the loop does not run and the count is 0.

#Trace it: the call stack

"Trust the smaller call" can feel like magic, but there is a plain mechanism behind it. When a function calls another function, the computer pauses the first one, remembers exactly where it was and what its variables held, and runs the new call. When that call returns, the paused one carries on. The paused calls wait in a pile called the call stack: newest on top, and only the top one is running.

Step through countFiles(["a", ["b", "c"], "d"]). The top row is the call stack, oldest call on the left.

countFiles(item):  if item is a file: return 1  total = 0  for each child in item:    total += countFiles(child)  return total

Every waiting call costs a little memory, because the computer has to remember where it paused. So recursion uses memory in proportion to how deep the calls go, even if you never create a list yourself.

#When recursion repeats itself

Some problems split into pieces that overlap. A classic is the Fibonacci sequence, 0, 1, 1, 2, 3, 5, 8, where each number is the sum of the two before it. The recursive version is one line: fib(n) = fib(n − 1) + fib(n − 2), with fib(0) = 0 and fib(1) = 1 as base cases. It is correct. It is also very slow.

Each call that is not a base case makes two more. The tree gets bushier fast: every time n goes up by 1, the number of calls grows by about 1.6 times. fib(4) makes 9 calls. fib(30) makes 2,692,537, almost all of them repeats. The fix is to remember answers you already worked out, which is the starting point of dynamic programming.

#Recursion or a loop

Anything recursive can be rewritten with a loop and a list you manage yourself as a stack. Here is how to choose:

• Use recursion when the data is nested: folders, trees, menus inside menus, JSON inside JSON. The code mirrors the shape of the data.
• Use recursion when the problem splits into smaller copies, as in merge sort and divide and conquer, or when you try choices one at a time, as in backtracking.
• Use a loop for a flat walk over a list. Summing 100,000 numbers recursively, one call per number, means 100,000 waiting calls. Python refuses at about 1,000 by default.

#Common mistakes

#Check yourself

#What to practise next

Next, Math for Algorithms covers the few formulas that make costs like these easy to estimate. To practise recursion now, solve Moving the Wedding Cake, where a few lines of recursion solve a puzzle that is awkward to write as a plain loop. Later, Tree Traversals uses exactly the folder pattern, and Backtracking uses it to try every combination.