Search
6 results for “call-stack”
Search results
Recursion & the Call Stack
Why CPython's recursion limit exists to protect the real, platform-dependent C stack rather than being an arbitrary language rule, and why raising it too high can still crash the interpreter instead of just allowing deeper recursion. Verified against CPython 3.12; exact stack behavior, default limit, and crash mode are interpreter- and version-specific, not universal across every Python implementation.
What does Python's recursion limit actually protect against, and is it just an arbitrary language-level rule?
It protects the real, underlying C stack the Python interpreter itself runs on, each level of recursion consumes real stack memory, and without a limit, sufficiently deep (or infinite) recursion would exhaust that stack and crash the interpreter process entirely, a hard C-level failure, not a clean Python exception. The limit converts that hard crash into a catchable `RecursionError` raised well before the actual stack is exhausted, which is exactly why it exists, a controlled failure mode is far better than an uncontrolled process crash, not an arbitrary restriction on how "should" write code.
Python's own documentation warns that raising the recursion limit "should be done with care, because a too-high limit can lead to a crash." Why doesn't raising the limit simply allow deeper, safe recursion?
The recursion limit is a proxy for the real constraint, actual available C stack space, which is platform-dependent and finite regardless of what the configured limit says. Setting the limit higher than the platform's actual available stack can support doesn't create more stack space, it just removes the early warning that would have raised a clean `RecursionError`, so recursion can now run deep enough to exhaust the real stack and crash the process with a low-level segmentation fault instead, a worse failure mode than the exception the limit was preventing in the first place.
Given the risk of hitting a recursion limit, when would you rewrite a recursive algorithm iteratively, and what does that actually trade away?
Rewrite iteratively when the recursion depth scales with input size in a way that could plausibly exceed the platform's real stack capacity, deep tree traversals, recursive descent over large or adversarial inputs, anything where "how deep" isn't bounded by a small constant. The trade is code clarity: many recursive algorithms (tree traversal, divide-and-conquer, backtracking) read far more naturally as recursion, mirroring the problem's own recursive structure, and converting them to an explicit-stack iterative version, while removing the depth risk entirely, usually costs some of that direct correspondence between code and problem structure.
A custom class defines __eq__ based on a value field but leaves __hash__ using default identity-based hashing. What actually goes wrong when you use an instance as a dict key?
In Python 3, simply defining `__eq__` without touching `__hash__` doesn't leave the old identity-based hash in place, Python automatically sets `__hash__` to `None` on that class, making instances unhashable, so using one as a dict key raises `TypeError` immediately rather than corrupting anything. This happens even if a parent class defines `__hash__`: overriding `__eq__` in a subclass sets that subclass's `__hash__` to `None` regardless of what the parent provides, ordinary inheritance does not carry the parent's hash forward. The silent, no-exception version of this bug only happens if the class explicitly keeps or re-supplies an identity-based `__hash__` alongside the value-based `__eq__` (e.g. `__hash__ = object.__hash__`, or, to retain a parent's hash on purpose, `__hash__ = Parent.__hash__`). In that case, two instances with the same value compare equal (`a == b` is `True`) but hash differently, and inserting under key `a` then looking up with an equal-but-distinct key `b` lands in the wrong hash bucket and returns nothing, because the hash mismatch never gave the lookup a chance to even check equality against the right entry.
For the same graph, why might you choose DFS over BFS even though BFS finds shortest paths and DFS doesn't?
Shortest-path guarantees aren't always the goal, DFS is a natural fit for exhaustively exploring all possibilities along one path before trying another (backtracking problems, detecting cycles, topological sorting, finding connected components), where the actual requirement is "visit everything reachable" or "explore this branch fully before trying the next," not "find the closest thing first." DFS via recursion is also often simpler to implement for these problems, at the cost of consuming call-stack depth proportional to how deep the graph goes, which matters for very deep or very large graphs where an iterative approach (or BFS) avoids the recursion-depth risk entirely.