When would you insist on the iterative form of binary search rather than the recursive one?
answer
- how deep can the recursion nest?
- depth equals the probe count
- about thirty frames at a billion entries
- frames are space: O(log n) versus O(1)
- both calls sit in tail position
basics
~20 sRarely on stack-depth grounds: recursion nests only floor(log2 n) + 1 deep, about 30 frames at a billion entries. Insist on the loop when the stack is genuinely tiny or already deep, or when per-call overhead matters in a hot path.
solid answer
~50 sHonestly the two forms are near-equivalent here, so I would usually choose for readability. The recursive form nests at most `floor(log2(n)) + 1` deep — about 30 frames for a billion candidates — so it costs O(log n) auxiliary space against the loop's O(1), a few hundred bytes. I would insist on the loop in concrete cases: a very small stack that gets audited statically, such as deeply embedded or interrupt-style code; a search already called from inside another deep recursion, where frames compound; a measured hot path where per-call overhead shows; or when I am unwilling to depend on the environment eliminating the calls. What I would not claim is that recursion risks overflow on large inputs — logarithmic depth is exactly what makes it safe. Both calls sit in tail position, so the rewrite needs no explicit stack.
code
pseudocode · 10 linesSEARCH(a, lo, hi, target):
if lo > hi:
return NOT_FOUND
mid = lo + (hi - lo) / 2
if a[mid] == target:
return mid
if a[mid] < target:
return SEARCH(a, mid + 1, hi, target)
else:
return SEARCH(a, lo, mid - 1, target)go deeper
Know that both forms do the same comparisons in the same order, and that the recursive one nests only about log2(n) calls deep — roughly thirty for a billion candidates, not millions.
State the space claim precisely: O(log n) auxiliary for the recursive form against O(1) for the loop, because call frames count as space. Explain why tail position makes the loop rewrite mechanical.
Give concrete circumstances rather than a preference — tiny audited stacks, a search nested inside another recursion, a measured hot path, or unwillingness to depend on call elimination — and refuse the overflow scare.
Own it as a standards question: when a team should mandate iterative forms across a codebase versus judging case by case, and what that costs in readability and review time relative to the risk actually removed.
## The two forms are the same algorithm Binary search can be written as a loop that updates two bounds, or as a function that narrows the bounds and calls itself on the surviving side. They perform identical comparisons in identical order and share the same `floor(log2(n)) + 1` probe bound. The only difference is where the shrinking range is stored: in two variables that get overwritten, or in a chain of call frames. That difference is real but small, and getting its *size* right is what this question tests. ## Depth is the probe count Each recursive call handles a range at most half the size of its caller's, so the nesting depth equals the probe count: about `log2(n)` frames. Concretely — 20 frames for a million candidates, 30 for a billion, 40 for a trillion, and under 60 for any collection that could physically exist. A frame here holds a couple of bounds and a return address. So the recursive form's auxiliary space is **O(log n)**, versus **O(1)** for the loop. Both statements matter: - against the claim "recursion uses no extra space" — it does; frames are space, and pretending otherwise is a direction-of-claim error that will cost you elsewhere; - against the claim "recursion will blow the stack on a large input" — it will not; a few dozen frames is nothing. If a recursive binary search ever overflows the stack, the cause is a bug that stops the range from shrinking, not the size of the data. A candidate who states both boundaries — it is not free, and it is not dangerous — is answering better than one who picks a side. ## When the loop genuinely wins There are real cases, and naming them specifically is what separates judgment from dogma. **Very small stacks.** Deeply embedded targets, interrupt-style handlers and similar constrained contexts sometimes budget the whole stack in single-digit kilobytes and audit worst-case depth statically. There, an O(1)-space routine is easier to certify than one whose depth is a function of input size, even though the function is tiny. The argument is about *provability*, not about the bytes. **Compounding depth.** If the search runs from inside another recursion — a tree walk that searches at every node, say — the logarithmic frames sit on top of whatever depth is already there. Each individual contribution is negligible; the habit of ignoring them all is not. **Hot inner paths.** In a loop executing a search millions of times over small ranges, per-call overhead and the constraints recursion places on register allocation can be measurable. This is a profile-first argument, never an assumption — and at these sizes the probe count is so small that call overhead can be a real fraction of the total. **Not relying on call elimination.** Both recursive calls are in tail position: the result of the recursive call is returned unchanged, with nothing left to do afterwards. Some execution environments turn that into a jump and use constant stack; others do not, and whether they do can depend on optimisation settings. If your correctness argument depends on the elimination happening, write the loop and stop depending on it. ## Why the rewrite is mechanical Because the calls are in tail position, converting to a loop is a purely local transformation: replace `return SEARCH(a, mid + 1, hi, target)` with `lo = mid + 1` and loop, and symmetrically for the other branch. Nothing needs saving across the call, so no explicit stack is required. This is worth contrasting with recursion that is *not* tail-shaped — a traversal that must do work after both child calls, for instance. There, converting to iteration means building an explicit stack, and you have moved the space from one place to another rather than removing it. The reason binary search converts so cleanly is precisely that it only ever continues on **one** side. ## The answer to give Lead with the honest verdict: for binary search this is a style choice, because logarithmic depth is tiny. Then show you know the exact bound and the exact space claim (O(log n) versus O(1)). Then name the specific circumstances that would flip you to the loop — constrained stacks, compounding depth, measured hot paths, unwillingness to depend on call elimination. Finish with the reason the rewrite is safe: tail position, no explicit stack needed. Anyone who instead warns darkly about stack overflow on big inputs has confused binary search with recursion whose depth grows linearly.
- Is stack overflow a realistic risk for recursive binary search on a huge input?No. Depth is `floor(log2(n)) + 1` — around 30 frames at a billion candidates and under 60 for anything storable. If a recursive binary search does overflow, that points to a bug in how the bounds move rather than to input size, and the fix is the bug, not the loop rewrite.
- Why does converting binary search to a loop need no explicit stack, when converting some other recursions does?Because binary search continues on exactly one side, and the recursive call's result is returned unchanged — nothing has to be remembered across it. Recursions that must combine results from two child calls do have pending work to store, so iterating them means building an explicit stack and moving the space rather than removing it.
- How would you justify the recursive form in a code review?On clarity: the recursive version states the shrinking-range idea directly and has no bound-update bookkeeping to get wrong, and its O(log n) space is a few hundred bytes. I would flag it only if the call site is inside another deep recursion, the environment audits stack depth statically, or a profile shows call overhead mattering in a hot path.
saying these in an interview costs you the question
- Claims recursion will overflow the stack on large inputs
- Says the recursive form uses no extra space
- Thinks the loop rewrite needs an explicit stack
- Claims recursion changes the asymptotic time
- Argues the choice from style alone, with no bound