Solving the Impossible: True, Zero-Overhead Tail Call Optimization in Python
Python is renowned for its elegance, readability, and vast ecosystem. But for functional programming enthusiasts, Python has a glaring, notorious limitation: It does not support Tail Call Optimization (TCO).
If you try to write an elegant, tail-recursive algorithm in Python, you will inevitably smash headfirst into the dreaded RecursionError: maximum recursion depth exceeded.
Guido van Rossum (Python's creator) has famously argued against adding TCO to the language, preferring explicit loops and keeping tracebacks clear for debugging. The community's response? We built "Trampolines"—decorators that yield functions or raise exceptions to clear the call stack.
The problem? Trampolines are slow. They introduce massive overhead by constantly throwing exceptions or managing generator states.
Today, we are going to solve this "unsolved" issue. We aren't going to use slow trampolines.…