RecPy is a precompiler designed to automatically transform recursive Python functions into equivalent iterative versions prior to execution. By operating directly on the program’s Abstract Syntax Tree (AST), it eliminates the need for programmers to manually rewrite algorithms using loops, accumulators, or continuations.
The tool applies two distinct language-independent strategies depending on the structure of the code:
Tail Recursion Conversion: When a recursive call is the very last operation in a function, RecPy replaces it with a simple loop without requiring any auxiliary data structures.
General Recursion Conversion: For recursive functions (excluding multiple recursion), RecPy applies eight AST rewriting rules to simulate recursion iteratively. It replaces the interpreter's native call stack with an explicit user-space stack of execution frames paired with a state variable that tracks where execution must resume.
Python does not perform Tail Call Optimization (TCO) as a deliberate design decision. While Python allows developers to manually raise the interpreter's recursion limit, doing so merely delays the crash and risks abruptly terminating the operating system process. Because the interpreter will not optimize recursion away, source-to-source transformation via tools like RecPy provides a structural workaround to bypass stack limits.
RecPy was evaluated against a benchmark corpus of 34 recursive functions—generating 46 iterative variants in total (12 via tail conversion and 34 via general conversion)—yielding four primary outcomes:
Broad Syntactic Coverage: The test corpus exercised 105 out of the 111 AST node constructs in the Python 3.13 grammar. The only 6 uncovered nodes correspond to execution-suspension features (yield, yield from, async def, async for, async with, and await), which belong to an asynchronous/generator control axis orthogonal to standard recursion.
Semantic Equivalence: Across all 46 generated iterative functions, automated hash-based output verification confirmed zero discrepancies—every transformed function returned the exact same result as its recursive counterpart for identical inputs.
Asymmetric Performance: The runtime benchmarks confirmed the theoretical trade-offs of both methods: Tail conversion accelerated execution across all 12 applicable functions, achieving a median speedup of 1.91x (and a mean of 2.27x) by completely eliminating function call overhead. General conversion introduced a median overhead of 1.72x (mean of 2.56x), running slower than the original recursive code in 31 out of 34 cases. This predictable cost stems from managing an explicit stack and state machine in user space rather than relying on the C-level interpreter stack.
Stack Overflow Prevention: By replacing nested recursive calls with a loop and heap-allocated frame stack, RecPy eliminates interpreter stack exhaustion by construction, enabling recursive logic to scale to deep inputs without hitting Python's recursion ceiling.