Recursion and Why Python (Doesn't) Love It 🌀

If in an interview you're asked to write factorial or Fibonacci numbers using recursion — go ahead. But if you use it often in real life...
Yes, recursion is conceptually beautiful, mathematically elegant, but if you get carried away, you can crash production and fill up all RAM with stack frames.

Let's break down what happens under the hood and why Python, unlike functional languages, doesn't like recursion.

1️⃣ The cost: call stack
Each function call is not free. It creates a new stack frame in memory. This frame stores local variables and the return address.
Imagine a Russian doll where each next doll weighs as much as the previous one. In Python, this "weight" falls on RAM.
A while or for loop uses one block of memory. Recursion consumes memory linearly (or exponentially) proportional to the call depth.

2️⃣ Why no tail call optimization
In languages like Haskell or C++, the compiler is smart. If the recursive call is the last action in the function (tail recursion), it replaces it with a simple jump (GOTO), without creating a new frame. This is called Tail Call Optimization (TCO).

In Python, TCO is not and will not be implemented. Guido van Rossum (BDFL) is fundamentally against TCO in Python. The argument is simple: "We want to see full error tracebacks." If you collapse the stack, you'll never know at which recursion level everything crashed.
Therefore, the limit of 1000 calls (default) is not a bug, but a safeguard against stack overflow. Can you increase it via sys.setrecursionlimit? Yes. But if you need to do that, there's a 99% chance you've made an architectural mistake.

3️⃣ When is recursion evil, and when is it necessary?
❌ Linear structures (e.g., lists): Computing factorial, Fibonacci numbers, or traversing a flat list. An iterative while/for loop will always be faster and more memory-efficient (O(1) memory vs O(N)).
✅ Branching structures (trees, graphs, nested dicts): Parsing JSON, traversing file systems, DOM trees, or algorithms like Divide and Conquer (QuickSort, MergeSort). Here recursion reduces cognitive load and makes code readable.

4️⃣ Remedy for slowdowns: @lru_cache
A classic example of foolishness is computing Fibonacci "head-on". Complexity O(2^n). This means that to compute the 50th number, the program will die before finishing.
The solution is Memoization.
The decorator @functools.lru_cache caches function call results. If the function has already been called with that argument, Python simply retrieves the ready value from the hash table. This turns exponential horror into linear complexity O(N).

In summary: Python is not Haskell or Lisp. Here, recursion is a second-class citizen. Use it for trees and graphs, but for everything else, there are loops.

#анатомия_питона