# How Big Is This Folder? Recursion

Work out how big a folder is when it holds folders, which hold more folders, as deep as anyone made them: why one loop, a loop in a loop and a loop per level all come up short, and the idea that fixes them, recursion.

Apprentice · Data Structures · Updated November 17, 2026

By Gregor Dzierzon

## After this lesson you can

- Explain recursion as solving a problem by calling the same function on a smaller piece of it
- Find the base case and the recursive case in a recursive function
- Choose between a fixed set of loops and recursion for a job, from how deep its data can nest

## Key takeaways

- One loop adds up one level of folders, a loop in a loop two; no fixed number of loops reaches every level, because a folder can always be one level deeper.
- Recursion solves a problem by handing a smaller piece of the same problem back to the same function, such as a folder's size from the sizes of the folders inside it.
- Every recursive function has a base case, small enough to answer straight away, and a recursive case that calls the function again on a smaller piece.
- Going in, the problem gets smaller; coming back out, the answers are built up, innermost first.
- Walking n folders this way hands each one to the function once: O(n) time.

**Before this:** every loop in Module 2 walked a line, one item after another: an array, a linked list, a queue. This lesson's data isn't a line.

You're writing a small app that tidies up a computer's disk. Its first feature is the one people ask for most: point it at a folder, and it says how big the folder is, so they can find what's eating their space. Your test folder is *Photos*. Its **Properties** window (**Get Info** on a Mac) says 1,982 MB.

Here's what's inside. *Photos* holds 12 MB of files of its own, and two folders, *2024* and *2025*. *2024* holds 300 MB of files and a *Beach Trip* folder with 450 MB. *2025* holds 200 MB and a *Birthday* folder with 120 MB, and *Birthday* holds a *Videos* folder with 900 MB.

![The Photos folder drawn as a tree. Photos (12 MB of files) at the top, branching to 2024 (300 MB) and 2025 (200 MB). Under 2024 is Beach Trip (450 MB). Under 2025 is Birthday (120 MB), and under Birthday is Videos (900 MB). Each folder also shows its total: Beach Trip 450 MB, 2024 750 MB, Videos 900 MB, Birthday 1,020 MB, 2025 1,220 MB, Photos 1,982 MB](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/e63b2d8fb5414ce6a90e436a27e2f07e.webp)

The same job turns up all over real work. A shop's categories hold categories, a comment thread holds replies to replies, and the JSON an API sends back holds objects inside objects. By the end of this lesson you'll have the idea every one of them uses, **recursion**. First, the folder.

## What would you try?

**One loop over the folder's files.** Add up every file in *Photos*: 12 MB. Properties said 1,982. The loop never looked inside *2024* or *2025*, so it missed almost everything.

**A loop in a loop.** For each folder inside *Photos*, loop over its files too: 12 + 300 + 200 = 512 MB. Better, but *Beach Trip*, *Birthday* and *Videos* are one level further down, and this code never opens them.

**One more loop for each level.** A third loop, inside the second, adds *Beach Trip* and *Birthday*: 1,082 MB. Still 900 MB short, because *Videos* is a fourth level down. A fourth loop finally says 1,982 MB, and the test passes. Then the first customer points the app at a folder five levels deep, and it's wrong again.

| What we tried | Levels it reaches | It reports | Where it breaks |
|---|---|---|---|
| One loop | 1 | 12 MB | every folder inside |
| A loop in a loop | 2 | 512 MB | the third level |
| A loop per level, four deep | 4 | 1,982 MB | the next folder anyone makes one level deeper |

Each try is fast enough: it touches every file it reaches once, O(n), read "big O of n". Speed isn't the problem. Reach is. Folders can nest as deep as anyone makes them, so there's no number of loops you could write that's always enough. The code is never finished.

## The questions that lead to it

**What's the difference between adding up *Photos* and adding up *2025*?** None, really. Each is "my own files, plus everything in the folders inside me". *2025* is smaller, that's all.

**So if you already had a function that adds up a folder, what would you do with *Birthday*?** Hand it to that function, and add what comes back. And the same for *2024*, *2025* and *Videos*.

**When does a folder need no help?** When there's nothing inside it but files. *Videos* adds up its own 900 MB and it's done.

So one function could do the whole job: add up this folder's own files, then hand each folder inside it to *the same function*, and add what comes back. It never needs to know how deep the folders go, because each call only ever handles one level.

## How it got its name

This idea was so useful that it got a name: **recursion** (read "rih-KUR-zhun"). It comes from the Latin for "running back": the function runs back to itself. Solving a problem by calling the same function on a smaller piece of it is recursion, and a function that does it is a **recursive function**.

You've met the idea before, away from a computer. Counting a set of nesting dolls works the same way: open the big doll, and the question "how many dolls are in here?" comes back about a smaller doll, down to a tiny solid one that doesn't open.

![Five nesting dolls in a row, from the large red doll down to the tiny solid blue one, each opened to show the next one inside: counting them is the same question again, about a smaller doll each time](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/3990a59f6a2f4d229ab0ed6cf752eb09.webp)

## Adding up a folder, in code

Each folder has a name, the size of its own files in MB, and a list of the folders inside it. `FolderSize` adds up the folder's own files, then calls itself for each folder inside. It prints each folder's total as it finishes, so you can see the order the answers come in:

```csharp
Folder photos = new Folder("Photos", 12, [
    new Folder("2024", 300, [new Folder("Beach Trip", 450, [])]),
    new Folder("2025", 200, [new Folder("Birthday", 120, [new Folder("Videos", 900, [])])]),
]);

int FolderSize(Folder folder)
{
    int total = folder.FilesMB;
    foreach (Folder inner in folder.Folders)
    {
        total += FolderSize(inner);
    }
    Console.WriteLine(folder.Name + ": " + total + " MB");
    return total;
}

FolderSize(photos);

record Folder(string Name, int FilesMB, List<Folder> Folders);
```

```text
Beach Trip: 450 MB
2024: 750 MB
Videos: 900 MB
Birthday: 1020 MB
2025: 1220 MB
Photos: 1982 MB
```

```java
record Folder(String name, int filesMB, List<Folder> folders) {}

int folderSize(Folder folder) {
    int total = folder.filesMB();
    for (Folder inner : folder.folders()) {
        total += folderSize(inner);
    }
    IO.println(folder.name() + ": " + total + " MB");
    return total;
}

void main() {
    Folder photos = new Folder("Photos", 12, List.of(
        new Folder("2024", 300, List.of(new Folder("Beach Trip", 450, List.of()))),
        new Folder("2025", 200, List.of(new Folder("Birthday", 120, List.of(new Folder("Videos", 900, List.of())))))));
    folderSize(photos);
}
```

```text
Beach Trip: 450 MB
2024: 750 MB
Videos: 900 MB
Birthday: 1020 MB
2025: 1220 MB
Photos: 1982 MB
```

```python
from dataclasses import dataclass


@dataclass
class Folder:
    name: str
    files_mb: int
    folders: list


def folder_size(folder):
    total = folder.files_mb
    for inner in folder.folders:
        total += folder_size(inner)
    print(f"{folder.name}: {total} MB")
    return total


photos = Folder("Photos", 12, [
    Folder("2024", 300, [Folder("Beach Trip", 450, [])]),
    Folder("2025", 200, [Folder("Birthday", 120, [Folder("Videos", 900, [])])]),
])
folder_size(photos)
```

```text
Beach Trip: 450 MB
2024: 750 MB
Videos: 900 MB
Birthday: 1020 MB
2025: 1220 MB
Photos: 1982 MB
```

```javascript
const photos = {
  name: "Photos", filesMB: 12, folders: [
    { name: "2024", filesMB: 300, folders: [{ name: "Beach Trip", filesMB: 450, folders: [] }] },
    { name: "2025", filesMB: 200, folders: [
      { name: "Birthday", filesMB: 120, folders: [{ name: "Videos", filesMB: 900, folders: [] }] },
    ] },
  ],
};

function folderSize(folder) {
  let total = folder.filesMB;
  for (const inner of folder.folders) {
    total += folderSize(inner);
  }
  console.log(`${folder.name}: ${total} MB`);
  return total;
}

folderSize(photos);
```

```text
Beach Trip: 450 MB
2024: 750 MB
Videos: 900 MB
Birthday: 1020 MB
2025: 1220 MB
Photos: 1982 MB
```

```typescript
type Folder = { name: string; filesMB: number; folders: Folder[] };

const photos: Folder = {
  name: "Photos", filesMB: 12, folders: [
    { name: "2024", filesMB: 300, folders: [{ name: "Beach Trip", filesMB: 450, folders: [] }] },
    { name: "2025", filesMB: 200, folders: [
      { name: "Birthday", filesMB: 120, folders: [{ name: "Videos", filesMB: 900, folders: [] }] },
    ] },
  ],
};

function folderSize(folder: Folder): number {
  let total = folder.filesMB;
  for (const inner of folder.folders) {
    total += folderSize(inner);
  }
  console.log(`${folder.name}: ${total} MB`);
  return total;
}

folderSize(photos);
```

```text
Beach Trip: 450 MB
2024: 750 MB
Videos: 900 MB
Birthday: 1020 MB
2025: 1220 MB
Photos: 1982 MB
```

Each language writes a folder in its own short way. C# and Java use a **record**, a one-line class that only holds data; Python uses a *dataclass*, which does the same; JavaScript and TypeScript write each folder as an object, and TypeScript names its shape with `type`. The function is the same in all five.

1,982 MB, the same as Properties, with no loop per level. Look at the order of the lines: *Photos* is the first folder the function is handed and the last to answer, because it can't finish until every folder inside it has.

## The two parts, on the smallest example

The folder walk branches, which makes it hard to watch one step at a time. So take the smallest nested thing there is: those nesting dolls, where each doll holds at most one doll. Each doll knows the doll inside it, or holds nothing when it's the solid one (`null`, or `None` in Python), like the train cars in *"Play Next" Without Moving Everyone: Linked Lists*:

```csharp
Doll largest = new Doll("Red", new Doll("Orange", new Doll("Yellow", new Doll("Green", new Doll("Blue", null)))));

int CountDolls(Doll doll)
{
    if (doll.Inside == null)
    {
        Console.WriteLine("The " + doll.Color + " doll is solid");
        return 1;
    }
    Console.WriteLine("Opening the " + doll.Color + " doll");
    return 1 + CountDolls(doll.Inside);
}

Console.WriteLine("Dolls in the set: " + CountDolls(largest));

class Doll
{
    public string Color;
    public Doll? Inside;

    public Doll(string color, Doll? inside)
    {
        Color = color;
        Inside = inside;
    }
}
```

```text
Opening the Red doll
Opening the Orange doll
Opening the Yellow doll
Opening the Green doll
The Blue doll is solid
Dolls in the set: 5
```

```java
class Doll {
    String color;
    Doll inside;

    Doll(String color, Doll inside) {
        this.color = color;
        this.inside = inside;
    }
}

int countDolls(Doll doll) {
    if (doll.inside == null) {
        IO.println("The " + doll.color + " doll is solid");
        return 1;
    }
    IO.println("Opening the " + doll.color + " doll");
    return 1 + countDolls(doll.inside);
}

void main() {
    Doll largest = new Doll("Red", new Doll("Orange", new Doll("Yellow", new Doll("Green", new Doll("Blue", null)))));
    IO.println("Dolls in the set: " + countDolls(largest));
}
```

```text
Opening the Red doll
Opening the Orange doll
Opening the Yellow doll
Opening the Green doll
The Blue doll is solid
Dolls in the set: 5
```

```python
class Doll:
    def __init__(self, color, inside):
        self.color = color
        self.inside = inside


def count_dolls(doll):
    if doll.inside is None:
        print(f"The {doll.color} doll is solid")
        return 1
    print(f"Opening the {doll.color} doll")
    return 1 + count_dolls(doll.inside)


largest = Doll("Red", Doll("Orange", Doll("Yellow", Doll("Green", Doll("Blue", None)))))
print(f"Dolls in the set: {count_dolls(largest)}")
```

```text
Opening the Red doll
Opening the Orange doll
Opening the Yellow doll
Opening the Green doll
The Blue doll is solid
Dolls in the set: 5
```

```javascript
class Doll {
  constructor(color, inside) {
    this.color = color;
    this.inside = inside;
  }
}

function countDolls(doll) {
  if (doll.inside === null) {
    console.log(`The ${doll.color} doll is solid`);
    return 1;
  }
  console.log(`Opening the ${doll.color} doll`);
  return 1 + countDolls(doll.inside);
}

const largest = new Doll("Red", new Doll("Orange", new Doll("Yellow", new Doll("Green", new Doll("Blue", null)))));
console.log(`Dolls in the set: ${countDolls(largest)}`);
```

```text
Opening the Red doll
Opening the Orange doll
Opening the Yellow doll
Opening the Green doll
The Blue doll is solid
Dolls in the set: 5
```

```typescript
class Doll {
  color: string;
  inside: Doll | null;

  constructor(color: string, inside: Doll | null) {
    this.color = color;
    this.inside = inside;
  }
}

function countDolls(doll: Doll): number {
  if (doll.inside === null) {
    console.log(`The ${doll.color} doll is solid`);
    return 1;
  }
  console.log(`Opening the ${doll.color} doll`);
  return 1 + countDolls(doll.inside);
}

const largest = new Doll("Red", new Doll("Orange", new Doll("Yellow", new Doll("Green", new Doll("Blue", null)))));
console.log(`Dolls in the set: ${countDolls(largest)}`);
```

```text
Opening the Red doll
Opening the Orange doll
Opening the Yellow doll
Opening the Green doll
The Blue doll is solid
Dolls in the set: 5
```

Every recursive function has the same two parts, and naming them is the first thing to do when you read one:

- **The base case** is the smallest version of the problem, answered straight away without calling the function again. Here it's the solid doll: `if (doll.Inside == null) return 1`. In `FolderSize` it's a folder with no folders inside: its loop runs zero times, and it answers with its own files.
- **The recursive case** is every bigger version, answered by calling the function again on a smaller piece and using what comes back. Here it's `1 + CountDolls(doll.Inside)`; in `FolderSize`, adding each inner folder's size.

## Going in, and coming back out

The function opens Red, Orange, Yellow and Green before it can answer anything, because each of those calls is waiting for the one inside it. Only the Blue doll answers straight away: 1. Then the answers come back out: Green gets 1 and answers 2, Yellow answers 3, Orange 4, and Red 5.

![The five dolls from Red to Blue, with arrows going in from each doll to the next, labeled "asks", and arrows coming back out, labeled with each doll's answer: Blue answers 1, Green 2, Yellow 3, Orange 4 and Red 5](https://fsdtrainingmedia.blob.core.windows.net/public/images/2026/11/f60a9826981043a0b4f329e6b239ced8.webp)

So a recursive call works in two directions: going in, the problem gets smaller; coming back out, the answers are built up. That's why *Beach Trip* printed before *2024*, and *Photos* came last. Where the waiting calls wait is the subject of *Where Do the Waiting Calls Wait? The Call Stack*.

## What it costs

| Job | Big-O | The everyday reason |
|---|---|---|
| Add up a folder tree of n folders | O(n) | Each folder is handed to the function once |
| Count a set of n dolls | O(n) | One call per doll |
| Calls waiting at once | one per level of the deepest path | Each folder waits for the folders inside it to answer |

**When a loop wins.** Recursion earns its place when the data branches and nests to a depth nobody can know ahead. For a straight line, like the dolls, a plain loop does the same job in the same O(n) and keeps no calls waiting, and for folders nested thousands of levels deep, even the folder tool needs a different plan. *5,000 Folders Deep: Recursion or a Loop?*, in the next chapter, shows both.

**Try it.** Add a *Snorkeling* folder with 80 MB inside *Beach Trip*. Before you run it, predict the new lines: *Snorkeling: 80 MB* comes first, *Beach Trip* becomes 530 MB, *2024* 830 MB, and *Photos* 2062 MB. `FolderSize` doesn't change.

## Check yourself

2 questions to try on the lesson page.

## So what

Whenever data holds smaller copies of its own shape (a folder in a folder, a reply to a reply), you don't need a loop for every level: answer the smallest version, and hand every bigger version a smaller piece. One function, any depth, including levels nobody has made yet.

## Key terms

- [Recursion](https://www.ask-codey.com/glossary/recursion-data-structures)
- [Base Case](https://www.ask-codey.com/glossary/base-case)
- [Recursive Case](https://www.ask-codey.com/glossary/recursive-case)

## Cheat sheets

- [How Big Is This Folder? Recursion](https://www.ask-codey.com/cheat-sheets/ds-recursion-cheat-sheet)

Source: https://www.ask-codey.com/lessons/ds-recursion
