Q: How do you choose between recursion and iteration?

Derive the choice from the shape of the problem, not from taste. I pick recursion when the data structure is itself recursive: tree and graph traversal, nested JSON, file systems, the DOM, backtracking (permutations, sudoku), divide and conquer (merge sort, quick sort). There the recursive code mirrors the problem's shape, making it markedly more readable and harder to get wrong. I pick iteration for linear traversals (arrays, lists, simple counters) and anywhere the depth could be large. A plain loop is readable, uses O(1) memory and is easy to debug. Call out the deciding factor explicitly: if the depth depends on user input (say, processing a structure of arbitrary depth), I don't rely on recursion — I can't guarantee the depth. In those cases I either write it iteratively with an explicit stack or impose a depth limit. A good closing line: "Recursion is memory I pay for readability; when the structure is recursive the price is worth it, in a flat loop it isn't."

Q: Why is naive recursive fibonacci so slow, and how would you improve it?

This question expects a three-tier answer — walking the tiers in order makes a strong impression. The problem: the fib(n) = fib(n-1) + fib(n-2) call tree branches in two at every level and recomputes the same sub-problems over and over. Computing fib(30) recomputes fib(10) thousands of times. Result: O(2^n) time, O(n) space (stack depth). Tier 1 — memoization (top-down): cache computed results in a map and check the cache at the top of the call. Each n is computed once → O(n) time, O(n) space (cache plus stack). Tier 2 — bottom-up iteration: start from fib(2) and work upward. Recursion disappears entirely → O(n) time, O(n) space if you keep the table. Tier 3 — keep only two variables: each step needs only the previous two values → O(n) time, O(1) space. Generalise at the end: "This is the classic dynamic-programming example — when you have overlapping subproblems, you apply either memoization or tabulation." If they want more, you can mention the O(log n) matrix-exponentiation variant.

Q: How do you compute the space complexity of a recursive function?

State the core principle: recursion's memory equals the maximum number of frames alive at once, i.e. the maximum depth — O(d). It's the depth that matters, not the total number of calls. Illustrate with examples — this comparison is what makes the answer strong: factorial(n): depth n → O(n) DFS on a balanced tree: depth log n → O(log n) DFS on a skewed (chain-like) tree: depth n → O(n) Naive fib(n): nearly 2^n total calls, but at most n frames on the stack at once → O(n) space, O(2^n) time. Explaining that distinction is a strong signal. Then count the extra memory: locals held in each frame (if you allocate an array or slice per frame, multiply by depth — O(n × k)), the memoization cache, and the result structure. Close with the practical note: tailrec (Kotlin) or an iterative rewrite drops the depth memory to O(1); an explicit stack moves the memory from the stack to the heap — same complexity, but the limit effectively disappears.

Q: How would you process an arbitrarily nested structure, such as a JSON configuration?

First pick the approach and justify it: the structure is recursive, so a recursive walk is the natural solution — the function does the same job at every level. Describe the algorithm: for each node check its type; if it's a primitive, handle it (base case); if it's an object or array, call yourself for each child (recursive case). If you need to track a path/prefix, pass it as a parameter (flatten(value, '$prefix.$key')). Then list the production-grade details — these are what actually differentiate answers here: A depth limit — if the input comes from outside (an API, a user-supplied file), cap the depth and fail with a clear error; otherwise malicious input can trigger a stack overflow. Cyclic references — if the object graph has cycles (possible with JS objects), track visited nodes in a Set/WeakSet or you get infinite recursion. An iterative variant for very deep data — write it with an explicit stack and the depth limit disappears. Edge cases — null, empty objects/arrays, unexpected types; define exactly what each returns. Closing line: "Recursion buys readability here, but if the input comes from an untrusted source I won't ship it without a depth limit and a cycle check."

Question 1

What is recursion? What parts must a correct recursive function have?

Accepted Answer

Start with the definition: recursion is breaking a problem into a smaller instance of the same problem and having the function call itself. Then state the two mandatory parts: a base case (the stopping condition — n == 0, node == null, an empty list) and a recursive case (shrink the problem and call itself). Add the third, often-forgotten condition: every call must move toward the base case, otherwise recursion never stops even though a base case exists. Give a concrete example and point out the parts: factorial(n) — base case returns 1 for n <= 1, recursive case is n * factorial(n - 1); n decreases by one each call, so termination is guaranteed. Finish with the complexity: O(n) time, O(n) space — because n frames sit on the call stack at once. Remembering to state the space is the single most important detail in this question.

Question 2

How do you choose between recursion and iteration?

Accepted Answer

Derive the choice from the shape of the problem, not from taste. I pick recursion when the data structure is itself recursive: tree and graph traversal, nested JSON, file systems, the DOM, backtracking (permutations, sudoku), divide and conquer (merge sort, quick sort). There the recursive code mirrors the problem's shape, making it markedly more readable and harder to get wrong. I pick iteration for linear traversals (arrays, lists, simple counters) and anywhere the depth could be large. A plain loop is readable, uses O(1) memory and is easy to debug. Call out the deciding factor explicitly: if the depth depends on user input (say, processing a structure of arbitrary depth), I don't rely on recursion — I can't guarantee the depth. In those cases I either write it iteratively with an explicit stack or impose a depth limit. A good closing line: "Recursion is memory I pay for readability; when the structure is recursive the price is worth it, in a flat loop it isn't."

Question 3

Why is naive recursive fibonacci so slow, and how would you improve it?

Accepted Answer

This question expects a three-tier answer — walking the tiers in order makes a strong impression. The problem: the fib(n) = fib(n-1) + fib(n-2) call tree branches in two at every level and recomputes the same sub-problems over and over. Computing fib(30) recomputes fib(10) thousands of times. Result: O(2^n) time, O(n) space (stack depth). Tier 1 — memoization (top-down): cache computed results in a map and check the cache at the top of the call. Each n is computed once → O(n) time, O(n) space (cache plus stack). Tier 2 — bottom-up iteration: start from fib(2) and work upward. Recursion disappears entirely → O(n) time, O(n) space if you keep the table. Tier 3 — keep only two variables: each step needs only the previous two values → O(n) time, O(1) space. Generalise at the end: "This is the classic dynamic-programming example — when you have overlapping subproblems, you apply either memoization or tabulation." If they want more, you can mention the O(log n) matrix-exponentiation variant.

Question 4

How do you compute the space complexity of a recursive function?

Accepted Answer

State the core principle: recursion's memory equals the maximum number of frames alive at once, i.e. the maximum depth — O(d). It's the depth that matters, not the total number of calls. Illustrate with examples — this comparison is what makes the answer strong: factorial(n): depth n → O(n) DFS on a balanced tree: depth log n → O(log n) DFS on a skewed (chain-like) tree: depth n → O(n) Naive fib(n): nearly 2^n total calls, but at most n frames on the stack at once → O(n) space, O(2^n) time. Explaining that distinction is a strong signal. Then count the extra memory: locals held in each frame (if you allocate an array or slice per frame, multiply by depth — O(n × k)), the memoization cache, and the result structure. Close with the practical note: tailrec (Kotlin) or an iterative rewrite drops the depth memory to O(1); an explicit stack moves the memory from the stack to the heap — same complexity, but the limit effectively disappears.

Question 5

How would you process an arbitrarily nested structure, such as a JSON configuration?

Accepted Answer

First pick the approach and justify it: the structure is recursive, so a recursive walk is the natural solution — the function does the same job at every level. Describe the algorithm: for each node check its type; if it's a primitive, handle it (base case); if it's an object or array, call yourself for each child (recursive case). If you need to track a path/prefix, pass it as a parameter (flatten(value, '$prefix.$key')). Then list the production-grade details — these are what actually differentiate answers here: A depth limit — if the input comes from outside (an API, a user-supplied file), cap the depth and fail with a clear error; otherwise malicious input can trigger a stack overflow. Cyclic references — if the object graph has cycles (possible with JS objects), track visited nodes in a Set/WeakSet or you get infinite recursion. An iterative variant for very deep data — write it with an explicit stack and the depth limit disappears. Edge cases — null, empty objects/arrays, unexpected types; define exactly what each returns. Closing line: "Recursion buys readability here, but if the input comes from an untrusted source I won't ship it without a depth limit and a cycle check."

Criterion	Recursion	Iteration
Readability (trees, nested data)	Very high — the code mirrors the shape of the problem	Lower — you must maintain a stack by hand
Readability (simple loop)	Feels artificial	Natural
Memory	O(depth) — the call stack	Usually O(1)
Stack overflow risk	Yes — when depth grows large	No
Speed	Slightly slower — call overhead	Slightly faster
Debugging	Harder — deep stack traces	Easier
When to choose	Trees/graphs, backtracking, divide and conquer	Linear traversal, or depth unknown or large

Recursion basics