# 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

```perl
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:

```perl
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:

```perl
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:

```perl
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:
  ```perl
  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`](../perlfunc/goto.md) for the full keyword
description and the shape constraints.

## `__SUB__` — anonymous self-reference

```perl
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:

```perl
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

```perl
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:

```perl
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.

## See also

- [`goto`](../perlfunc/goto.md) — the keyword behind `goto &fn`.
- [`caller`](../perlfunc/caller.md) — works through goto’d frames
  with the same numbering as ordinary frames.
- [Arguments and `@_`](arguments.md) — `@_` semantics under
  `goto &fn`.
- [Declaration](declaration.md) — anonymous subs, the substrate
  for `__SUB__` and trampolines.
- [Scoping](scoping.md) — closures, the substrate for
  trampolines.