Recursion traced with a directory tree

A recursive directory counter pauses its current call while another call counts a child directory. When the child returns, the parent continues from the point where it paused. If you know loops and are learning recursion, following those pauses is more useful than imagining that the function starts over with all its variables shared.

Use an in-memory tree for the first trace. A file is represented by None; a directory is a dictionary from a name to another file or directory. The function counts files, not directories. An empty dictionary is therefore a valid directory containing zero files. This model is deliberately smaller than a filesystem so that permissions, links, and concurrent edits do not obscure the call behavior.

A call owns its own subtotal

Consider a root directory containing readme.txt, a src directory with two files, and an empty drafts directory. The root should return three. Every invocation has a local total, and a child’s local variable does not overwrite the parent’s variable with the same name.

def count_files(node):
    if node is None:
        return 1
    total = 0
    for child in node.values():
        total += count_files(child)
    return total

project = {
    "readme.txt": None,
    "src": {"app.py": None, "test_app.py": None},
    "drafts": {},
}
assert count_files(project) == 3
assert count_files({}) == 0

The None case is an explicit base case. The empty directory is another terminating case, expressed through the loop: there are no children to visit, so the function returns its initial subtotal of zero. Using if not node: return 1 would confuse the empty dictionary with the file marker and incorrectly count an empty directory as a file.

When the root begins, its subtotal is zero. Its first child is a file, so that call returns one immediately. The root adds one. It then calls count_files for src and pauses with its subtotal still equal to one. The src invocation initializes a different subtotal to zero, receives one from each of its two file children, and returns two. Only then does the root update its subtotal to three.

View full-size image ↗

The tree contains six nodes: three files and three directories including the root. The stack snapshot shows just the active path root, src, app.py. It does not contain every node already visited or every sibling still waiting.

Why adding the results is correct

The proof follows the data shape. A file contains exactly one file, itself, and the base case returns one. Assume each child call correctly counts the files in that child’s subtree. If the directory’s child subtrees do not overlap, every descendant file belongs to exactly one of them. Adding their counts gives the directory’s file count without omission or duplication.

The non-overlap assumption is doing real work. Two names that refer to the same object are still two child entries in this representation; the function would count the object twice. A directory that contains a reference back to itself would never reach a base case along that path. The proof applies to finite trees, with no cycles and one parent per non-root node.

Termination follows because each child is strictly below its parent in a finite tree. Eventually the path reaches a file or empty directory. The input contract is more useful than saying that recursion always stops when there is a base case somewhere in the function. A base case that the chosen recursive path never reaches cannot stop that path.

Count visits and simultaneous frames separately

Let N be the total number of file and directory nodes and H the maximum number of nodes on a root-to-leaf path. Each node receives one call, and each directory entry is examined once. Under constant-cost dictionary iteration and integer addition, total work is Θ(N). The number of simultaneously active calls is O(H).

A directory with one million file children has a large amount of work but a shallow stack. A chain of one million nested directories has a deep stack even if each directory has only one child. Both examples have roughly the same number of visits. Their memory risks differ because pending calls follow depth, not breadth.

Python limits interpreter recursion depth to protect the underlying stack. The documentation for sys.setrecursionlimit warns that a limit set too high can crash the interpreter. Raising the setting is not a general solution for untrusted directory depth. An explicit stack can hold pending nodes in ordinary heap memory, where you can enforce your own limit and report a useful error.

An explicit pending list changes the memory tradeoff

You can also count files by storing nodes waiting to be processed. Pop one node, count it if it is a file, or append its children if it is a directory. This version avoids recursive calls but can hold many siblings at once.

def count_files_pending(node):
    pending = [node]
    total, maximum_pending = 0, 1
    while pending:
        current = pending.pop()
        if current is None:
            total += 1
        else:
            pending.extend(current.values())
            maximum_pending = max(maximum_pending, len(pending))
    return total, maximum_pending

broad = {f'file{i}': None for i in range(4)}
deep = {'a': {'b': {'c': None}}}
assert count_files_pending(broad) == (4, 4)
assert count_files_pending(deep) == (1, 1)
assert count_files(broad) == 4
assert count_files(deep) == 1

The broad tree has one directory and four files. Recursive traversal needs at most two active frames, while the pending-list version holds four file entries after expanding the directory. The deep tree has three directories and one file along a single path. Its recursive traversal needs four frames, while its pending list never holds more than one node.

View full-size image ↗

The figure compares active recursive frames with pending-list entries, not their byte sizes. A Python frame and a list reference do not occupy the same amount of memory. Both versions still refer to the original tree, whose storage is separate from their traversal overhead.

The pending-list implementation still visits each node once, so it performs Θ(N) work. Its pending storage can be O(N), even for a shallow tree. Replacing recursion with a stack does not automatically preserve O(H) auxiliary storage; the contents of that stack matter. An explicit stack of paused child iterators can mimic recursive frames and retain the depth-based bound, but requires more bookkeeping than the simple node list.

Distinguish a file marker from a file identity

Every file in this teaching model uses the same marker, None. Four occurrences still represent four file entries. A global visited set of id(node) values would treat those four markers as one object and undercount them. If the application needs distinct physical files, its data model must carry an appropriate identity instead of this shared marker.

Shared directory objects create another distinction. If two names refer to the same dictionary, the counter traverses that dictionary through both names. If a dictionary contains itself, traversal does not terminate. The finite-tree assumptions exclude both cases from the proof that each node is visited once. Checking for active-path cycles and deduplicating every previously seen target are different policies, with different counts for shared subtrees.

For a learning exercise, keep the finite tree model and trace both functions on the broad and deep inputs before running them. Record which call is paused or which entries are pending after each step. A correct final count alone does not explain the memory difference; the sequence of stored state does.

Moving the example onto a real filesystem

A filesystem traversal needs a policy for symbolic links. Following a link can introduce a cycle or revisit an already counted target. Python’s os.walk does not follow directory links by default; its documentation also warns that enabling link traversal does not make it track previously visited directories for you.

There is a second policy question: are you counting directory entries or distinct underlying files? Hard links can give one file multiple names. Deduplicating by an appropriate file identity changes the answer and requires a visited set. That set adds memory beyond the call stack. A deleted file during traversal also forces a choice between failing, skipping, or recording an incomplete result.

Keep these concerns outside the first recursion exercise, then add them explicitly when building a tool. To practice the call mechanics, draw the local subtotal next to every frame before a child returns. Test an empty root, a single file marker, and a long directory chain. The resulting trace should show exactly where each returned count is added and which parent remains paused while the addition waits.