Skip to interview prep
Apexed

71. When should you prefer recursion over iteration, and what does every recursive function need?

EasyRecursion & backtracking

Technical
Show model answer

Every recursive function needs at least one base case that returns without recursing, and each recursive call must make progress towards a base case; otherwise it recurses until the stack overflows. Recursion fits naturally when the problem is self-similar: trees, divide and conquer, backtracking and grammars.

Iteration avoids call overhead and stack-depth limits, so it is usually preferable for simple linear processes (summing a list, walking a linked list). Any recursion can be converted to iteration with an explicit stack. In an interview, pick the clearer version and mention the stack depth, for example "this recursion is O(n) deep, which could overflow for a list of a million nodes".

When should you prefer recursion over iteration, and what does every recursive function need — Data structures & algorithms interview question — Apexed