@call_once python macro for unlimited recursion depth

I like competitive programming (like Meta Hacker Cup). Where you solve algorithmic puzzles in limited time. In many problems, a recursive solution feels more natural than an iterative one — but Python’s recursion depth limit (usually around 1000) makes it impractical for larger inputs.

So I built a small macro — @call_once — that lets you write recursive functions with virtually unlimited recursion depth.

Example

Let’s take a simple Fibonacci example:

def fib(n):

    if n <= 1:

        return n

    return fib(n - 1) + fib(n - 2)



print(fib(200_000) % 1_000)

This will crash immediately — Python’s call stack can’t handle that depth.


But with one decorator:

@call_once

def fib(n):

    if n <= 1:

        return n

    return fib(n - 1) + fib(n - 2)



print(fib(200_000) % 1_000)

…it runs fine, limited only by memory.

Internals

To achieve unlimited recursion, we simulate the call stack in user space.


The macro rewrites the function’s AST into a continuation-style version.


For example, our fib becomes something like this:

def fib_aux(n):

    if n <= 1:

        return ('result', n)



    fib_n_1_args = (n - 1,)

    if fib_n_1_args not in fib_CACHE:

        return ('call', fib_n_1_args)



    fib_n_2_args = (n - 2,)

    if fib_n_2_args not in fib_CACHE:

        return ('call', fib_n_2_args)



    return ('result', fib_CACHE[fib_n_1_args] + fib_CACHE[fib_n_2_args])

We do two main things:

1. Check if recursive results are already cached.


2. If not, return 'call' — meaning we need to compute that subcall.

Main loop

The wrapper function implements the “virtual stack”:

while stack:

    current_args = stack.pop()

    typ, value = fn(*current_args)

    if typ == 'call':

        stack.append(current_args)

        stack.append(value)

        continue

    if typ == 'result':

        cache[current_args] = value

Each frame is just a tuple of arguments.


If the inner call returns 'call', we push its arguments and continue.


This way, recursion happens in our heap-allocated stack, not Python’s C stack — so it never overflows.

The stack also behaves like an ordered set — the same arguments aren’t pushed twice, hence the name call_once.

Performance

To compare, let’s use an iterative Fibonacci:

def fib_fast(n):

    lst = [0] * (n + 1)

    lst[0] = 0

    lst[1] = 1

    for i in range(2, n + 1):

        lst[i] = lst[i - 1] + lst[i - 2]

    return lst[n]

Results (see fib.call_once.py):

fib_fast time:     1.10 seconds, result: 125

@call_once fib time: 1.29 seconds, result: 125

The overhead is small — within ~20%.


But it deserves deeper benchmarking on more complex recursion patterns.

Real-world use case

I first needed this macro during the Meta Hacker Cup 2025, in the problem A2: Snake Scales (Chapter 2).

Problem: facebook.com/codingcompetitions/hacker-cup/2025/round-1/problems/A2

You’re given a list of platform heights, e.g.:

4 2 5 6 4 2 1

Each number is the height of a platform.


You can climb between platforms using a ladder.


You can reach a platform either:

• From the ground (ladder length ≥ platform height), or


• From a neighbor (ladder length depending on the height difference).

The goal: find the minimal ladder length that allows visiting all platforms.

Recursive solution

We define a helper function min_left(n) — the minimal ladder length needed to reach platform n from the left or ground:

def min_left(n):

    from_ground = A[n]

    if n == 0:

        return from_ground

    dist = abs(A[n] - A[n - 1])

    from_left = max(min_left(n - 1), dist)

    return min(from_ground, from_left)

Then, compute the minimal ladder length overall:

mn = 0

for i in range(len(A)):

    min_from_both = min(min_left(i), min_right(i))

    mn = max(mn, min_from_both)

With @call_once, this works even for arrays of length 100_000 — still within time limits.

Full code: hackercup/a2.py

Summary

@call_once lets you write naturally recursive algorithms in Python without worrying about the recursion limit.


It works by rewriting your function into a manual stack loop that executes calls iteratively, preserving performance close to iterative code.

It’s ideal for competitive programming, graph traversals, dynamic programming, or any case where recursion feels right but Python says “RecursionError: maximum recursion depth exceeded”.