5,000 Folders Deep: Recursion or a Loop?
Keep the folder tool working on a folder thousands of levels deep, where recursion runs out of call stack: why a bigger limit and a plain loop both fall short, how a loop with a pile of its own does the job, and how to choose between recursion and a loop for any task.
Journeyman · Data Structures · Updated
After this lesson you can
- Rewrite a recursive function as a loop, using your own stack when the data branches
- Choose between recursion and a loop for a task, and explain the choice
Key takeaways
- Recursion keeps one frame waiting per level, and the call stack runs out in the thousands: Python stops at 1,000 calls.
- A bigger limit only moves the crash, and a loop with one variable follows one branch and misses the rest.
- A straight line, like the dolls, becomes a plain loop; branches, like folders, become a loop with a stack of your own: the pile the call stack kept for you.
- Choose recursion when the data is nested and not too deep, a loop when it's a line, and a loop with your own stack when the nesting can be very deep; all three are O(n) time.
- Your own stack lives in ordinary memory, which has room for millions of entries where the call stack has room for thousands.
Before this: Where Do the Waiting Calls Wait? The Call Stack showed that recursion keeps one frame waiting for every level it's inside, on a stack with room for thousands.
The folder tool is out in the world, and a new ticket arrives. A customer's backup program went wrong one night and copied a folder into itself, then into the copy, and so on: her Backup folder is now 5,000 levels deep. The Python version of the tool stops at once with RecursionError: maximum recursion depth exceeded. Nothing is looping this time, so the base case isn't the problem: every call is a real folder, one level further down, and the bottom really is there. It's just 5,000 calls away, and Python allows 1,000.
The other languages go further. In our measurements a simple recursive function ran out at about 10,000 calls in JavaScript, 18,000 in Java and 24,000 in C#, and fewer when each call keeps more. So her drive works in C#, but a chain of 100,000 folders crashes all five. You can't promise customers their folders will stay shallow.
What would you try?
Raise the limit. Python's sys.setrecursionlimit(10_000) gets her 5,000 levels through. The next customer has 30,000, and in C# there's no limit to raise and nothing to catch: the whole program stops. Like the bigger stack in The Folder Tool That Never Stopped, it moves the crash further out.
A loop with one variable. No recursion, so no frames: start at the top folder, add its files, move the variable into the folder inside, and repeat. On her chain of backups, where each folder holds exactly one folder, it's perfect. On the Photos folder it says 762 MB: it went Photos, 2024, Beach Trip and stopped, because one variable can follow one branch. 2025, Birthday and Videos never got a look.
| What we tried | How deep it can go | Photos (1,982 MB) | Where it breaks |
|---|---|---|---|
| Recursion | about 1,000 in Python, more elsewhere | 1,982 MB | a chain deeper than the call stack |
| Recursion, limit raised | as deep as the new limit | 1,982 MB | the next, deeper drive; C# can't raise it |
| A loop with one variable | any depth | 762 MB | a folder with two folders inside |
All of them are O(n) time for what they reach. The recursion is right but runs out of room; the loop has room but loses the branches.
The questions that lead to it
What was the call stack keeping for us? Every folder that was started but not finished: while FolderSize was deep inside 2024, the frame for Photos was waiting, still holding the fact that 2025 hadn't been looked at yet.
Why did that run out? Because the call stack is small: a few megabytes, set aside for calls.
Could we keep that pile ourselves? Yes: a list of folders still to visit, in ordinary memory, where all your other lists live and there's room for millions. Take a folder off the pile, add its files, and put the folders inside it on the pile. When the pile is empty, every folder has been added.
How it got its name
Solving a problem by repeating with a loop, instead of a function calling itself, is called an iterative solution (iterate means to repeat). And the pile is the stack from Undo the Last Thing First: Stacks: you take the newest folder off the top, last in, first out, exactly as the call stack handed back the newest call first. You're keeping by hand what the call stack kept for you.
A straight line: a plain loop
The one-variable loop was the right idea for a straight line. The nesting dolls from How Big Is This Folder? Recursion are one: each doll holds at most one doll, so recursion that makes one call follows a single path, and a loop can walk the same path with one variable:
Doll largest = new Doll("Red", new Doll("Orange", new Doll("Yellow", new Doll("Green", new Doll("Blue", null)))));
int count = 0;
Doll? doll = largest;
while (doll != null)
{
count++;
doll = doll.Inside;
}
Console.WriteLine("Dolls in the set: " + count);
class Doll
{
public string Color;
public Doll? Inside;
public Doll(string color, Doll? inside)
{
Color = color;
Inside = inside;
}
}
Dolls in the set: 5
class Doll {
String color;
Doll inside;
Doll(String color, Doll inside) {
this.color = color;
this.inside = inside;
}
}
void main() {
Doll largest = new Doll("Red", new Doll("Orange", new Doll("Yellow", new Doll("Green", new Doll("Blue", null)))));
int count = 0;
Doll doll = largest;
while (doll != null) {
count++;
doll = doll.inside;
}
IO.println("Dolls in the set: " + count);
}
Dolls in the set: 5
class Doll:
def __init__(self, color, inside):
self.color = color
self.inside = inside
largest = Doll("Red", Doll("Orange", Doll("Yellow", Doll("Green", Doll("Blue", None)))))
count = 0
doll = largest
while doll is not None:
count += 1
doll = doll.inside
print(f"Dolls in the set: {count}")
Dolls in the set: 5
class Doll {
constructor(color, inside) {
this.color = color;
this.inside = inside;
}
}
const largest = new Doll("Red", new Doll("Orange", new Doll("Yellow", new Doll("Green", new Doll("Blue", null)))));
let count = 0;
let doll = largest;
while (doll !== null) {
count++;
doll = doll.inside;
}
console.log(`Dolls in the set: ${count}`);
Dolls in the set: 5
class Doll {
color: string;
inside: Doll | null;
constructor(color: string, inside: Doll | null) {
this.color = color;
this.inside = inside;
}
}
const largest = new Doll("Red", new Doll("Orange", new Doll("Yellow", new Doll("Green", new Doll("Blue", null)))));
let count = 0;
let doll: Doll | null = largest;
while (doll !== null) {
count++;
doll = doll.inside;
}
console.log(`Dolls in the set: ${count}`);
Dolls in the set: 5
The recursive version kept five frames waiting on the call stack; the loop keeps one count and one doll, and moves along.

Branches: a loop with a stack of your own
Folders branch, so the loop keeps a to-do pile. This version adds up Photos again, records the order it visits the folders, and then adds up a chain of 100,000 folders, 1 MB each, which crashes the recursive FolderSize in every one of the five languages:
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, [])])]),
]);
Folder deep = new Folder("Level 100000", 1, []);
for (int level = 99999; level >= 1; level--)
{
deep = new Folder("Level " + level, 1, [deep]);
}
List<string> visited = new List<string>();
int FolderSize(Folder top)
{
int total = 0;
Stack<Folder> toDo = new Stack<Folder>();
toDo.Push(top);
while (toDo.Count > 0)
{
Folder folder = toDo.Pop();
visited.Add(folder.Name);
total += folder.FilesMB;
foreach (Folder inner in folder.Folders)
{
toDo.Push(inner);
}
}
return total;
}
Console.WriteLine("Photos: " + FolderSize(photos) + " MB");
Console.WriteLine("Visited: " + string.Join(", ", visited));
Console.WriteLine("A chain 100000 folders deep: " + FolderSize(deep) + " MB");
record Folder(string Name, int FilesMB, List<Folder> Folders);
Photos: 1982 MB
Visited: Photos, 2025, Birthday, Videos, 2024, Beach Trip
A chain 100000 folders deep: 100000 MB
record Folder(String name, int filesMB, List<Folder> folders) {}
List<String> visited = new ArrayList<>();
int folderSize(Folder top) {
int total = 0;
ArrayDeque<Folder> toDo = new ArrayDeque<>();
toDo.push(top);
while (!toDo.isEmpty()) {
Folder folder = toDo.pop();
visited.add(folder.name());
total += folder.filesMB();
for (Folder inner : folder.folders()) {
toDo.push(inner);
}
}
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())))))));
Folder deep = new Folder("Level 100000", 1, List.of());
for (int level = 99999; level >= 1; level--) {
deep = new Folder("Level " + level, 1, List.of(deep));
}
IO.println("Photos: " + folderSize(photos) + " MB");
IO.println("Visited: " + String.join(", ", visited));
IO.println("A chain 100000 folders deep: " + folderSize(deep) + " MB");
}
Photos: 1982 MB
Visited: Photos, 2025, Birthday, Videos, 2024, Beach Trip
A chain 100000 folders deep: 100000 MB
from dataclasses import dataclass
@dataclass
class Folder:
name: str
files_mb: int
folders: list
photos = Folder("Photos", 12, [
Folder("2024", 300, [Folder("Beach Trip", 450, [])]),
Folder("2025", 200, [Folder("Birthday", 120, [Folder("Videos", 900, [])])]),
])
deep = Folder("Level 100000", 1, [])
for level in range(99999, 0, -1):
deep = Folder(f"Level {level}", 1, [deep])
visited = []
def folder_size(top):
total = 0
to_do = [top]
while len(to_do) > 0:
folder = to_do.pop()
visited.append(folder.name)
total += folder.files_mb
for inner in folder.folders:
to_do.append(inner)
return total
print(f"Photos: {folder_size(photos)} MB")
print("Visited: " + ", ".join(visited))
print(f"A chain 100000 folders deep: {folder_size(deep)} MB")
Photos: 1982 MB
Visited: Photos, 2025, Birthday, Videos, 2024, Beach Trip
A chain 100000 folders deep: 100000 MB
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: [] }] },
] },
],
};
let deep = { name: "Level 100000", filesMB: 1, folders: [] };
for (let level = 99999; level >= 1; level--) {
deep = { name: `Level ${level}`, filesMB: 1, folders: [deep] };
}
const visited = [];
function folderSize(top) {
let total = 0;
const toDo = [top];
while (toDo.length > 0) {
const folder = toDo.pop();
visited.push(folder.name);
total += folder.filesMB;
for (const inner of folder.folders) {
toDo.push(inner);
}
}
return total;
}
console.log(`Photos: ${folderSize(photos)} MB`);
console.log(`Visited: ${visited.join(", ")}`);
console.log(`A chain 100000 folders deep: ${folderSize(deep)} MB`);
Photos: 1982 MB
Visited: Photos, 2025, Birthday, Videos, 2024, Beach Trip
A chain 100000 folders deep: 100000 MB
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: [] }] },
] },
],
};
let deep: Folder = { name: "Level 100000", filesMB: 1, folders: [] };
for (let level = 99999; level >= 1; level--) {
deep = { name: `Level ${level}`, filesMB: 1, folders: [deep] };
}
const visited: string[] = [];
function folderSize(top: Folder): number {
let total = 0;
const toDo: Folder[] = [top];
while (toDo.length > 0) {
const folder = toDo.pop()!;
visited.push(folder.name);
total += folder.filesMB;
for (const inner of folder.folders) {
toDo.push(inner);
}
}
return total;
}
console.log(`Photos: ${folderSize(photos)} MB`);
console.log(`Visited: ${visited.join(", ")}`);
console.log(`A chain 100000 folders deep: ${folderSize(deep)} MB`);
Photos: 1982 MB
Visited: Photos, 2025, Birthday, Videos, 2024, Beach Trip
A chain 100000 folders deep: 100000 MB
The stack is Stack<T> in C# and an ArrayDeque in Java, with push and pop. Python and JavaScript have no separate stack type: a list or an array is the stack, adding with append or push and taking the last one with pop. In TypeScript, pop() might return undefined on an empty array, so the ! after it says "the loop already checked: there's one there".
1,982 MB again, and the 100,000-level chain, which no call stack could hold, is just a pile that never holds more than one folder at a time. Look at the order, though. The pile hands back the newest folder first, so 2025, put on last, is visited right after Photos, and 2024 comes near the end. For a total the order doesn't matter. When it does (printing an outline, say), put the inner folders on the pile in reverse.
Which reads better?
Both versions do the same work: every folder once, O(n) time. The difference is how easy the code is to read, and how deep it can go.
| The data | Reads better as | Why |
|---|---|---|
| A straight line: dolls, a linked list, a countdown | A loop | One path, so one variable can follow it |
| Nested, a few levels deep: a menu, a page's sections, a small org chart | Recursion | The code mirrors the data: handle one level, call yourself for the rest |
| Nested and possibly very deep: a user's folders, a long reply chain | A loop with your own stack | It can't overflow the call stack |
The cost card
| Recursion | A loop with your own stack | |
|---|---|---|
| Time for n folders | O(n) | O(n) |
| Memory at worst | O(depth) frames, on a stack with room for thousands | O(n) entries in the pile, in memory with room for millions |
| What it can't do | go deeper than the call stack | (nothing here; it's just more lines to read) |
The memory isn't less with your own stack, and for a very wide folder the pile can even hold more entries than recursion keeps frames. What changes is where it lives: in the same large area of memory as all your other lists, instead of the small call stack.
In your textbook. Some languages turn a call made as a function's very last step, called a tail call, into a jump that reuses the frame, so that kind of recursion never overflows. None of this course's five languages promises to do it, so don't count on it: when the depth can be large, write the loop.
Try it. In the stack version, change the loop that puts the inner folders on the pile so it puts them on in reverse order, and run it again. The folders now come out as Photos, 2024, Beach Trip, 2025, Birthday, Videos: the order a recursive walk opens them.
Check yourself
2 questions to try on the lesson page.
So what
You're never stuck with one or the other. Write recursion when the data is nested and the code reads like the data, a loop when it's a line, and a loop with your own stack when the nesting might be deep enough to overflow, which, for anything users create, it can be.