Recursion#

Subs may call themselves, each other, or — with a bit of ceremony — replace their own call frame and pass control elsewhere without growing the stack. This page covers the four mechanisms: ordinary recursion, mutual recursion, goto &fn tail calls, and __SUB__ for anonymous self-reference. It also covers the depth limit you will hit if you ignore them.

Plain recursion#

sub factorial {
    my ($n) = @_;
    return 1 if $n <= 1;
    return $n * factorial($n - 1);
}

factorial(10);                   # 3628800

Each recursive call adds a new frame to Perl’s call stack. The stack costs memory and a fixed per-call overhead; for shallow recursion this is irrelevant, for deep recursion it is the bottleneck.

Perl emits a ”Deep recursion on subroutine X“ warning when a sub recurses past 100 levels deep (compile-time threshold, PERL_SUB_DEPTH_WARN). The warning is in the recursion category — no warnings 'recursion' silences it. The only hard limit is the OS stack, typically 8 MiB by default, controllable with ulimit -s.

For deep, structurally-recursive workloads, prefer one of:

An explicit work queue (iterative reformulation).
Tail recursion via goto &fn (see below).
A trampoline (see below).

Mutual recursion#

Two subs that call each other:

sub is_even {
    my ($n) = @_;
    return 1 if $n == 0;
    return is_odd($n - 1);
}

sub is_odd {
    my ($n) = @_;
    return 0 if $n == 0;
    return is_even($n - 1);
}

is_even(10);                     # 1

Mutual recursion has no special treatment from the runtime — it is just two subs happening to call each other. The same depth limit applies.

If is_even is defined first and refers to is_odd before is_odd exists, you’ll see a ”Bareword not allowed“ or ”Called undefined subroutine“ depending on the call shape. Predeclare to fix:

sub is_odd;                      # forward declaration
sub is_even { ... is_odd($n-1) }
sub is_odd  { ... is_even($n-1) }

`goto &fn` — tail-call forwarding#

The goto &SUBROUTINE form replaces the current frame with a call to another sub. The current frame is gone — it is not on the stack — so the call does not grow the stack:

sub api_v2 {
    my @args = @_;
    push @args, deprecated => 1;
    @_ = @args;
    goto &api_v1;                # tail-call: api_v1 sees the modified @_
}

This is the right tool when:

A wrapper sub needs to forward to a real implementation without leaving a stack frame behind. Decorators, logging shims, AUTOLOAD dispatchers.

A recursive sub can express its recursion as ”do some work, then become this other call“. Classic tail recursion:

sub factorial_tail {
    my ($n, $acc) = @_;
    $acc //= 1;
    return $acc if $n <= 1;
    @_ = ($n - 1, $n * $acc);
    goto &factorial_tail;
}

factorial_tail(20);            # 2432902008176640000, no stack growth

The mechanics: @_ becomes the called sub’s argument array, the current frame is unwound, control jumps. The caller of the current sub will see the result of the goto’d-to sub, never the one it called.

goto &fn is the only form of goto that performs a tail call. The label-based form (goto LABEL) is unrelated and far more restricted.

See goto for the full keyword description and the shape constraints.

`SUB` — anonymous self-reference#

use feature 'current_sub';                # or use v5.16

my $factorial = sub {
    my ($n) = @_;
    return 1 if $n <= 1;
    return $n * __SUB__->($n - 1);
};

$factorial->(5);                 # 120

__SUB__ evaluates to a code reference to the currently-running sub. It is the only way to recurse into an anonymous sub without storing it in a named variable first (and without leaking a strong reference to it from inside itself, the classic memory-leak shape).

For anonymous subs that do not need to recurse, prefer the plain anonymous form. __SUB__ exists for the recursion case specifically.

Trampolines#

When you want bounded-stack recursion but goto &fn is awkward (because the recursion is mutual, or branches into many sub-cases), the trampoline pattern works:

sub trampoline {
    my $next = shift;
    while (ref $next eq 'CODE') {
        $next = $next->();
    }
    return $next;
}

sub even {
    my ($n) = @_;
    return $n == 0 ? 1 : sub { odd($n - 1)  };
}

sub odd {
    my ($n) = @_;
    return $n == 0 ? 0 : sub { even($n - 1) };
}

trampoline(even(10000));         # 1, no stack growth

Each ”recursive“ call returns a closure to be invoked next, rather than calling itself directly. The trampoline drives the closures in a loop. The stack stays at depth 2 forever.

Trampolines are heavier than goto &fn (one closure allocation per ”call“), but they generalise to arbitrary control flow — including continuations and CPS-style code. For production Perl, goto &fn is the usual choice; trampolines appear when the structure of the recursion makes goto clumsy.

The depth limit, in practice#

sub recurse {
    my ($n) = @_;
    return $n if $n <= 0;
    return recurse($n - 1);
}

recurse(2000);                   # warning: Deep recursion on subroutine
                                 # (default limit 1000)

The ”Deep recursion“ warning is informational, not fatal — it fires once per sub. You will run out of actual stack space well before any practical limit on most platforms. If you see this warning, the answer is almost always to refactor (iterative loop, goto &fn, or trampoline), not to raise the limit.

If you have already verified the recursion is bounded and you just want to suppress the noise, scope the warning category:

no warnings 'recursion';

This silences the warning entirely; it does not change the OS stack limit, which is what eventually terminates a runaway recursion regardless of warnings.