Recursion

Part I · Module 10 · Chapter 10.9 · Recursion

1. A Subroutine That Calls Itself

use strict;
use warnings;

my $design = {
    top => {
        alu  => { add => {}, mul => {} },
        fifo => {},
    },
};

sub walk {
    my ($node, $name, $depth) = @_;
    printf "%s%s\n", ("  " x $depth), $name;
    walk($node->{$_}, $_, $depth + 1) for sort keys %$node;
    return;
}

walk($design->{top}, "top", 0);

top
  alu
    add
    mul
  fifo

Five nodes at three different depths, printed correctly indented, by a subroutine of four lines that contains no loop over levels.

The $depth parameter is the trick that makes the output readable, and it is worth noticing that the subroutine never computes it — each call passes $depth + 1 down, so every node knows how deep it is because its parent told it. That is the general pattern for anything a recursive subroutine needs to know about where it is: pass it as a parameter.

Note sort keys %$node rather than bare keys. Chapter 6.5 established that hash order varies between runs, so without the sort this output would come out in a different order each time — and a hierarchy dump is exactly the kind of output someone will diff.

This structure has no explicit base case, and it terminates anyway: sort keys %$node on an empty hash is an empty list, so the for runs zero times and the call returns. An empty container is an implicit base case, which is why walking a finite tree often needs no return guard. §2 is about when you do.

2. The Base Case

use strict;
use warnings;

my $calls = 0;

sub depth_of {
    my ($node) = @_;
    $calls++;
    return 0 unless ref $node eq "HASH";          # THE BASE CASE
    my $max = 0;
    for my $k (sort keys %$node) {
        my $d = depth_of($node->{$k});
        $max = $d if $d > $max;
    }
    return 1 + $max;
}

my $tree = { a => { b => { c => 1 } } };
printf "depth=%d after %d call(s)\n", depth_of($tree), $calls;

depth=3 after 4 call(s)

Three levels of hash, and four calls — one for each of the three hashes and one for the leaf value 1, which hit the base case and returned 0 without recursing.

The base case here is unless ref $node eq "HASH", and its position matters: it is the first thing after the arguments are unpacked. That ordering is not stylistic — everything below it assumes $node is a hash reference.

Move the guard below the keys %$node line and the subroutine works on every internal node and then fails:

Can't use string ("1") as a HASH ref while "strict refs" in use at wrong-order.pl line 7.

255

It was the leaf that killed it — the value 1 under key c, reached on the third level down. The top two levels are hash references and dereference happily, so a shallow test passes and the failure arrives only once the recursion reaches real data. Chapter 7.3 §7 measured that error family; the guard is what keeps the rest of the body safe from it.

The shape of a recursive subroutine

Steps 3 and 4 are the two exits — a call takes one or the other, never both. Step 2 before step 4 is the requirement, and inverting them is how a recursive subroutine dies on a leaf rather than looping forever.

3. No Base Case

use strict;
use warnings;

my $n = 0;

sub forever {
    $n++;
    die "ABORT at depth $n\n" if $n > 120;        # my own bound, so this ends
    return forever();
}

forever();

Deep recursion on subroutine "main::forever" at no-base-case.pl line 9.
ABORT at depth 121

255

The die on line 9 is mine. Without it that subroutine does not stop — the only Perl diagnostic is the first line, and it is a warning.

4. Recursion Against an Explicit Stack

Every recursion can be rewritten as a loop with your own stack, and it is worth knowing both.

use strict;
use warnings;

my $tree = { a => { b => {} }, c => {} };

sub count_rec {
    my ($node) = @_;
    my $c = 1;
    $c += count_rec($node->{$_}) for sort keys %$node;
    return $c;
}

my $recursive = count_rec($tree);

my @stack = ($tree);
my $iterative = 0;
while (@stack) {
    my $node = pop @stack;
    $iterative++;
    push @stack, values %$node;
}

printf "recursive=%d  iterative=%d  same=%s\n",
    $recursive, $iterative, ($recursive == $iterative ? "yes" : "no");

recursive=4  iterative=4  same=yes

Same answer, four nodes either way. The two forms differ in three respects:

Prefer recursion when the problem is naturally recursive, which a hierarchy is. The recursive count_rec says "a node counts as one plus its children"; the loop says "maintain a worklist". The first is the definition, the second is a mechanism.

Two reasons to reach for the stack instead:

• Depth that could genuinely be large. Each Perl call frame costs real memory, so a recursion a million deep is a problem where a million-element array is not. For design hierarchies and directory trees this never arises; for a linked structure it might.
• You need the traversal order to be breadth-first. pop gives depth-first, shift gives breadth-first — and a recursive subroutine is depth-first by construction. Chapter 9.3 §5 noted that while (@queue) with pushes inside is the shape for a growing worklist, and this is that shape.

Note the stack version used values %$node rather than sort keys — because the order is already determined by push/pop rather than by the loop, so sorting would have to happen on the way out instead. That asymmetry is a small example of the general point: the recursive version keeps ordering local to each level, where it is easy to control.

5. What to Pass Down and What to Return Up

The two halves of a recursive subroutine's interface, and the commonest mistake in each.

Pass down anything a call needs to know about its position: the depth, the path so far, a $seen hash, the accumulating prefix. Each of those is a parameter with a default on the first call:

sub walk {
    my ($node, $path, $depth) = @_;
    $path  //= "";
    $depth //= 0;
    ...
    walk($node->{$_}, "$path/$_", $depth + 1) for sort keys %$node;
}

The mistake here is using a file-scoped variable instead, which works until the subroutine is called twice:

my $depth = 0;                       # file scope
sub walk {
    $depth++;
    ...
    walk($node->{$_}) for sort keys %$node;
    $depth--;                        # and now you must remember to undo it
}

That is the same bug shape Chapter 9.8 §5 measured for a retry counter shared across items — the second traversal inherits the first one's state — with the extra hazard that the $depth-- has to run on every exit path, including early returns and dies.

Return up a single value per call, and let the caller combine. depth_of in §2 returns a number and the parent takes the maximum; count_rec in §4 returns a count and the parent adds. Both are one scalar, which keeps Chapter 10.6's context question from arising.

When a recursive subroutine needs to return several things, return one reference — Chapter 10.8 §2's shape:

sub summarise {
    my ($node) = @_;
    return { nodes => 1, leaves => 1 } unless ref $node eq "HASH" && %$node;
    my %acc = (nodes => 1, leaves => 0);
    for my $k (sort keys %$node) {
        my $sub = summarise($node->{$k});
        $acc{nodes}  += $sub->{nodes};
        $acc{leaves} += $sub->{leaves};
    }
    return \%acc;
}

Returning (@a, @b) from a recursive call would flatten at every level — Chapter 10.8 §1 — and the damage compounds with depth, because each level merges its children's already-merged lists.

6. Why This Matters in Engineering Work

Design hierarchies are the canonical case. A netlist, a module tree, an instance path — none has a depth fixed at script-writing time, and all of them are walked by the shape in §1. The same is true of dependency closure, where a filelist can include another filelist.

The base-case-first ordering is what keeps it from dying on leaves. A hierarchy walker that dereferences before testing works on every internal node and fails on the first leaf, which in a wide tree is most of the data.

And the deep-recursion warning is not a safety net. It fires once, at 100, as a warning, and is absent entirely from any script without use warnings. A cyclic structure — which hand-edited configuration files do contain — produces a job that runs until the machine complains. An explicit depth bound costs one line and turns that into a message naming the likely cause.

7. Common Mistakes

No base case. The only diagnostic is a single warning at depth 100, and the program keeps going.

Testing the base case after dereferencing. It dies on the first leaf instead.

Relying on Deep recursion as an error. It is a warning, fires once, and is silent without use warnings.

no warnings "recursion" to quieten a legitimately deep walk. That removes the only signal for the runaway case.

No depth bound on untrusted input. A cycle makes it run until memory is exhausted.

Position tracked in a file-scoped variable. A second call inherits the first one's state, and the decrement must run on every exit path.

Returning a list from a recursive call. It flattens at every level, and the loss compounds with depth.

Bare keys in a walker whose output is read. The order varies between runs.

8. Exercise

Exercise 1 — the walk. Build §1's three-level $design and walk it with indentation. Confirm the five lines. Then remove the sort and run it five times, recording how many distinct orders you get.

Exercise 2 — the implicit base case. Explain in one sentence why §1's walk terminates without a return guard. Then add a leaf value — fifo => "a string" — and record what happens.

Exercise 3 — the base case and the call count. Write depth_of from §2 on a three-level hash and record the depth and the call count. Then account for each of the four calls.

Exercise 4 — the wrong order. Move depth_of's base-case test to after the keys %$node line. Record the error and say which node triggered it.

Exercise 5 — no base case. Write §3's forever with your own die bound at 120. Record both STDERR lines and the exit status. Say which line Perl produced and which was yours.

Exercise 6 — the threshold. Measure the Deep recursion warning count at depths 99, 100 and 101. Then add no warnings "recursion" and measure again. Finally remove use warnings entirely and measure once more.

Exercise 7 — the depth bound. Add a die at depth 200 to a walker, then build a cyclic structure — $n->{self} = $n — and run it. Record the message and the exit status.

Exercise 8 — both ways. Count the nodes of a four-node tree recursively and with an explicit stack. Confirm they agree. Then change pop to shift and describe how the traversal order changed.

Exercise 9 — returning several things. Write §5's summarise returning a hash reference with nodes and leaves. Then rewrite it to return ($nodes, $leaves) as a list and record what the top-level caller receives for a three-level tree.

9. Summary

• A subroutine that calls itself walks data whose depth is a property of the input, not of the code.
• Pass position down as parameters — depth, path, a $seen hash — rather than keeping it in a file-scoped variable, which a second call would inherit.
• An empty container is an implicit base case, which is why walking a finite tree often needs no explicit guard.
• Write the base case first, before anything that dereferences the node. Measured: three levels, depth 3, four calls — the fourth was the leaf hitting the base case.
• Deep recursion fires at exactly depth 100, exactly once — measured 0 / 1 / 1 at depths 99 / 100 / 101.
• It is a warning, not an error. Execution continues; a missing base case consumes memory until something external stops it.
• It is the recursion warnings category and is silent with no use warnings, so it is absent from many older scripts.
• Bound the depth explicitly for input you did not create — a cycle is the usual cause, and Chapter 7.10 §5 has the $seen guard.
• Return one scalar per call and let the parent combine; return one reference when a call has several results, because a returned list flattens at every level.
• An explicit stack is equivalent — measured, 4 nodes both ways — and is worth it only for genuinely large depth or for breadth-first order.

Chapter 10.10 covers the other thing a subroutine can keep: a variable that outlives the block it was created in, giving a counter or a configured helper with private state.