Recursion vs Iteration and Memory

Problem

A service stores hierarchical data as a tree and computes its depth with the obvious recursive function. In production it crashes on a particular customer's data with a RecursionError, even though the tree has only 50,000 nodes and the machine has gigabytes of memory.

1. Explain what memory a recursive call consumes, why the crash depends on the shape of the tree rather than its size, and why the interpreter refuses long before physical memory runs out.
2. Rewrite the depth computation iteratively with an explicit stack, so it handles any shape, and show that the recursive and iterative versions agree on ordinary trees.
3. State the space complexity of both versions precisely, and describe when recursion is still the right choice.

• Tree nodes have left and right children; a "degenerate" tree is a chain where every node has only one child.
• Do not raise the recursion limit as the fix. Explain why that is a bandage.

Examples

• Balanced tree of 50,000 nodes: depth about 16, recursion depth 16, both versions run fine.
• Chain of 50,000 nodes: depth 50,000. The recursive version needs 50,000 simultaneous frames; CPython's default limit is 1,000, so it raises RecursionError after about 1,000 calls. The iterative version pushes at most 50,000 entries onto a list and returns 50,000.
• Chain of 5,000 nodes in Python with the limit raised to 10,000: works. Before CPython 3.11 every Python call also consumed C stack, so a 10⁶-deep recursion would overflow the 8 MB C stack and segfault long before the heap ran out. Since 3.11 pure-Python frames live on the heap, so 10⁶ deep merely costs on the order of 100 MB of frame objects, and any C-level call in the chain (a __lt__ inside max, a json decode) still has a separate, smaller C limit.

Hints

1. What is stored per call: return address, saved registers, local variables, and in CPython a frame object. Where does it live, and how big is that region?
2. Recursion depth equals the length of the longest path being explored, not the number of nodes. What is that for a chain?
3. An explicit stack is a list on the heap. What does it store per entry, and what limits its size?