Recursion Finally Clicked When I Built a File Tree Walker

I understood the definition of recursion — a function that calls itself — for a long time before I actually understood what was happening when it ran. The gap closed when I stopped reading toy factorial examples and instead traced, frame by frame, what happens when a function walks a real nested folder structure on disk. This post is that same walkthrough: a working directory tree walker in PHP, with the actual call stack drawn out at each level, because seeing the stack is what made the mechanism click, not another restatement of "it calls itself."

Why factorial examples didn't do it for me

Most recursion tutorials start with factorial or Fibonacci, and I think that's part of why it stays abstract for so long — those examples work on plain numbers, so there's nothing visually different between one call and the next to anchor the mental model to. A file tree is different: each recursive call is visibly operating on a different, smaller piece of a real, inspectable structure, and you can print exactly what each level of the recursion is looking at as it happens.

The problem: print every file in a folder, including subfolders

Given a folder that might contain files, and might contain subfolders that themselves contain more files and subfolders arbitrarily deep, print every file's path. The folder structure isn't known in advance — it could be one level deep or ten.

project/
  README.md
  src/
    Controller.php
    Models/
      User.php
      Post.php
  tests/
    UserTest.php

The recursive function

function walkDirectory(string $path, int $depth = 0): void
{
    $indent = str_repeat('  ', $depth);
    $entries = scandir($path);

    foreach ($entries as $entry) {
        if ($entry === '.' || $entry === '..') {
            continue;
        }

        $fullPath = $path . DIRECTORY_SEPARATOR . $entry;

        if (is_dir($fullPath)) {
            echo "{$indent}[DIR] {$entry}\n";
            walkDirectory($fullPath, $depth + 1); // the recursive call
        } else {
            echo "{$indent}{$entry}\n";
        }
    }
}

walkDirectory('project');

Two things make this recursive rather than just a loop: the function calls itself (walkDirectory($fullPath, $depth + 1)) when it finds a subdirectory, and each call is a genuinely separate invocation with its own $path, its own $entries, and its own $depth — nothing is shared between them except what's explicitly passed as an argument.

Tracing the actual call stack

This is the part that made it click. Here's what the call stack literally looks like at the moment the function reaches User.php, deep inside src/Models/:

walkDirectory('project', 0)              <- outermost call, still running
  walkDirectory('project/src', 1)              <- called from inside the above, still running
    walkDirectory('project/src/Models', 2)      <- called from inside that, still running
      # currently printing 'User.php' from inside this frame

Every one of those three walkDirectory calls is simultaneously alive on the call stack at that moment — none of them have returned yet, because each one is in the middle of its own foreach loop, paused at the line where it called deeper. The outermost call hasn't finished processing project/'s entries; it's just waiting, mid-loop, for the call it made into src/ to finish before it moves on to project/'s next entry (tests/). Understanding that every level is genuinely paused and waiting, not finished, is the specific insight that factorial examples never made concrete for me — with a file tree, you can point at exactly which real folder each paused frame corresponds to.

The base case: what actually stops the recursion

Nothing in the function above has an explicit "stop here" check, and that can look like a bug — but the base case is implicit in the data itself: scandir() on a folder with no subdirectories returns entries that are all files, so the is_dir($fullPath) check is never true, no recursive call happens, and that branch of the recursion simply ends because there's nothing left to descend into. This is worth calling out explicitly because a lot of recursion bugs come from a missing or wrong base case, and it's easy to assume every recursive function needs a visible if (something) { return; } line — sometimes the base case is just "the data ran out," expressed as a loop that has nothing left to trigger another call.

• The recursive case: entry is a directory, so recurse one level deeper into it.
• The base case (implicit): entry is a file, so just print it and continue the current loop — no deeper call happens.

What happens if the base case is wrong

To make the failure mode concrete rather than theoretical, here's what happens if the directory check is accidentally inverted:

// Bug: recurses into files instead of directories
if (! is_dir($fullPath)) {
    walkDirectory($fullPath, $depth + 1);
}

Running this against the sample tree throws a warning from scandir() the moment it tries to treat README.md as a directory, because scandir() on a file path fails. If the check had instead been something that could recurse forever without ever failing outright — for example, following a symbolic link that points back to a parent folder, which real filesystems allow — the practical symptom would be a fatal "maximum function nesting level reached" error once PHP's call stack limit is hit, rather than a clean failure. That's the general risk with any recursive function operating on real filesystem or graph data: a base case that depends on the data eventually running out can be defeated by data that cycles back on itself, which is exactly why production-grade directory walkers usually track visited paths explicitly rather than trusting the folder structure to always terminate on its own.

When recursion is the right tool, and when it isn't

A file tree is a genuinely good fit for recursion because the problem is self-similar at every level — "process this folder" always reduces to "process each entry, and for directories, process this same problem one level deeper," with the exact same logic at every depth. Recursion earns its complexity when a problem has that self-similar, arbitrarily-nested shape. It's usually the wrong tool for a simple linear scan (a plain loop is clearer and doesn't carry call-stack overhead), and for extremely deep or unbounded recursion depth, an explicit stack-based iterative version avoids the "maximum function nesting level" failure entirely, at the cost of managing that stack by hand instead of letting the language's call stack do it implicitly.

Rewriting it iteratively, with an explicit stack

Every recursive function can be rewritten to use an explicit stack data structure instead of the language's own call stack, and doing this once for a function you already understand recursively is a genuinely good way to see exactly what the call stack was doing implicitly, because now you're managing that same "what's paused and waiting" state yourself, visibly, in a variable you can inspect.

function walkDirectoryIterative(string $rootPath): void
{
    $stack = [[$rootPath, 0]]; // each entry: [path, depth]

    while (! empty($stack)) {
        [$path, $depth] = array_pop($stack);
        $indent = str_repeat('  ', $depth);

        foreach (scandir($path) as $entry) {
            if ($entry === '.' || $entry === '..') {
                continue;
            }

            $fullPath = $path . DIRECTORY_SEPARATOR . $entry;

            if (is_dir($fullPath)) {
                echo "{$indent}[DIR] {$entry}\n";
                $stack[] = [$fullPath, $depth + 1]; // push instead of calling
            } else {
                echo "{$indent}{$entry}\n";
            }
        }
    }
}

The $stack array here is doing explicitly, in code you can print and inspect at any point, exactly what the language's call stack was doing invisibly in the recursive version — each pushed entry is a folder that's been discovered but not yet processed, the same as a paused recursive call waiting for a deeper one to finish. The one real behavioral difference: this specific iterative version processes folders in a different order than the recursive one (depth-first but not in the same left-to-right sequence, because array_pop takes from the end), which is worth noticing if the exact traversal order matters for what you're building — a queue instead of a stack (array_shift instead of array_pop) would give you breadth-first order instead, visiting all of one depth level before descending further.

Counting as you walk, without a second pass

A common next step once the basic walk works is tallying something while traversing — total file count, total size, or matching a pattern. Because each recursive call only knows about its own subtree, the running total has to be threaded through as a return value rather than a variable the outer call can just read directly:

function countFiles(string $path): int
{
    $count = 0;

    foreach (scandir($path) as $entry) {
        if ($entry === '.' || $entry === '..') {
            continue;
        }

        $fullPath = $path . DIRECTORY_SEPARATOR . $entry;

        if (is_dir($fullPath)) {
            $count += countFiles($fullPath); // add the subtree's count to ours
        } else {
            $count++;
        }
    }

    return $count;
}

Each recursive call returns its own subtree's count, and the caller adds that returned number to its own running total — nothing is shared or mutated across calls, which is exactly why this pattern is safe to reason about even in a deeply nested tree. If you're auditing a real codebase and want a rough sense of how much text lives in a given file before writing tooling like this to walk it programmatically, a plain word counter on a sample file is a faster first check than writing a script for a one-off question.

Turning this into something you can actually verify

The best way to confirm you actually understand a recursive function, rather than just having watched someone else trace it, is to write down by hand what you'd expect the call stack to look like at a specific point, then add a var_dump($depth) or an actual debugger breakpoint at that exact point and check whether reality matches your prediction. I was wrong about my own prediction the first time I tried this on the file walker above — I'd assumed the outer call finishes processing src/ entirely before starting tests/, which is true, but I'd mentally pictured the src/Models/ call as already "done" by the time tests/ starts, when in fact by then it genuinely has finished and returned — getting that distinction right by checking it against real output, rather than assuming, is what turned this from something I could recite into something I actually trusted myself to reason about in a code review. If you're building the habit of verifying assumptions like this with real tests rather than by eye, writing your first automated test suite for a small PHP app covers the same instinct applied more broadly.