Noesis
1.2.39 · D5Introduction to Programming (Python)

Question bank — Recursion depth limit — stack overflow

1,460 words7 min read↑ Back to topic
🇮🇳 Yeh page Hinglish mein padho →

True or false — justify

Each recursive call adds exactly one new stack frame.
True. A call is paused mid-work, so its locals, arguments and return address must be saved in a fresh stack frame while the inner call runs — one call, one frame.
A correct base case guarantees you will never hit a RecursionError.
False. A reachable base case stops infinite recursion, but a correct-yet-deep recursion (e.g. depth 2000) still exceeds the ~1000-frame limit before reaching the base.
RecursionError and a stack-overflow segfault are the same crash.
False. The RecursionError is Python's catchable soft-limit warning fired before memory runs out; a segfault is the OS's uncatchable hard crash that the soft limit exists to prevent.
Raising sys.setrecursionlimit() gives you more stack memory.
False. It only raises the counter Python is willing to reach; the actual stack memory (fixed, ~1–8 MB) is unchanged. Push past what memory can hold and you segfault anyway.
An iterative loop uses one stack frame no matter how many times it repeats.
True. A loop stays inside a single call, reusing the same frame; it updates variables in place instead of stacking new frames, so depth stays 1.
The default recursion limit means you can always make 1000 of your own recursive calls.
False. The limit counts all live frames — the REPL, the module, the caller. If already exist, you get roughly of your own.
Catching RecursionError with try/except lets your program recover gracefully.
True. Because it's an ordinary exception (not an OS signal), try/except can catch it and return a fallback — this is the whole reason Python uses a soft limit.
Two recursive branches (like fib(n-1) + fib(n-2)) double the recursion depth.
False. They multiply the total number of calls, but at any instant only one path down the tree is active, so depth grows linearly (≈ ), not exponentially.
Deeper recursion always uses more heap memory.
False. Frames live on the stack, not the heap. Deep recursion strains the stack; heap usage depends on what objects you allocate, which is a separate concern (see Memory model — stack vs heap).
Tail recursion in Python avoids growing the stack.
False. Python does not do tail-call optimization, so even a tail-recursive call pushes a new frame — see Tail recursion and why Python lacks tail-call optimization.

Spot the error

def f(n): return f(n) — the base case is missing. Is that the only bug?
The missing base case is the cause, but note the deeper issue: even with a base like if n==0, calling f(n) (unchanged argument) never approaches it — so it'd still loop forever.
def g(n):``if n == 0: return 0\` return g(n + 1) — base is n==0. Safe?
Unsafe. The recursive step moves away from 0 (increasing n), so the base is unreachable from a positive start → guaranteed RecursionError.
sys.setrecursionlimit(10**9) before a broken infinite recursion — good fix?
No. A huge limit removes the early warning and lets the runaway recursion exhaust real stack memory, turning a debuggable RecursionError into an uncatchable segfault.
except RecursionError: placed around a call that's already 900 frames deep. Reliable?
Risky. Handling the exception itself needs a little stack room; if you're right at the ceiling, even the except block can fail to run. Leave headroom rather than skimming the limit.
def h(n): if n <= 0: return 0`` return n + h(n - 1)called ash(2000)`. What's wrong?
Logically nothing — the base is reachable and approached. The bug is purely depth: 2000 stacked frames exceed the default 1000 limit.

Why questions

Why does the interpreter need to store a return address in each frame?
So it knows where to resume in the caller after the current call returns — without it, execution couldn't come back to the right spot.
Why is the stack small (~1–8 MB) while the heap is huge?
The stack is a fast, fixed, contiguous region for call bookkeeping (push/pop only); the heap is a large, flexible pool for long-lived objects. Small size is the price of that speed and simplicity.
Why does Python choose a soft limit instead of letting the OS crash the program?
A catchable RecursionError lets you debug, log, or recover; a raw OS segfault gives no traceback and cannot be handled — the soft limit trades a small guardrail for graceful failure.
Why does converting recursion to iteration fix depth problems?
Iteration keeps all work inside one frame and updates variables in place, so no frames pile up — depth stays 1 regardless of the input size (see Iteration vs Recursion).
Why does "depth" matter more than "total number of calls" for overflow?
Overflow is about frames alive at once. A function called a million times sequentially (each returning before the next) never stacks — only simultaneously-paused calls consume stack space.
Why can the actual crash depth differ slightly between runs or environments?
Because pre-existing frames (REPL, imported modules, wrapping functions) vary, and the limit counts all frames — so your usable depth shifts with whatever's already on the stack.

Edge cases

What is the recursion depth of a function that never calls itself?
One while it runs (its own frame), and it never contributes to overflow — recursion depth in the "stacking" sense is effectively the extra frames beyond that.
Base case n == 0 but the function is called with n = -1 decreasing by 1 each step. What happens?
It overshoots the base (-1, -2, -3, ...), never equals 0, and overflows. Robust code uses n <= 0 so any starting side is caught.
sys.setrecursionlimit(5) then a recursion that needs depth 10. What error, and is the number "5" exact?
RecursionError fires, but not at your 5th call — pre-existing frames count too, so it may trip almost immediately. The limit is a total-frame ceiling, not a per-function budget.
A recursion of exactly the limit depth: does it always crash, or can it just barely succeed?
It's borderline — since the limit counts all frames, whether one more fits depends on how many were already stacked, so the same code can pass in one context and raise in another.
Does mutual recursion (a calls b, b calls a) hit the same limit?
Yes. The limit counts every frame regardless of which function it belongs to, so ping-ponging between two functions stacks frames just as fast as self-recursion.
Zero-argument or constant recursion like def loop(): return loop() — what's the depth pattern?
Depth climbs by exactly 1 per call (no argument to track a "distance to base"), so it races straight to the limit and raises RecursionError — a pure "no base case" failure.
Recall One-line safety checklist before you trust a recursion

Does it have a base case? ::: It must, or frames never stop. Does every recursive call move strictly toward that base? ::: If not, the base is unreachable and you overflow anyway. Is the maximum depth comfortably under ~1000? ::: If not, raise the limit only for finite depth, or rewrite iteratively.

Connections