What is Recursion? How does it relate to the Call Stack?
Recursion and Call Stack
Recursion is a technique in which a function calls itself to solve a problem by reducing it to smaller instances of the same problem. A recursive solution requires a base case to terminate the recursion.
Each recursive call creates a new stack frame containing local variables, parameters, and the return address. These frames remain on the call stack until the recursive calls return. Excessive recursion can therefore cause stack overflow.
- 1
Every recursive solution needs a termination condition.
- 2
Each call creates a call-stack frame.
- 3
Recursive calls are unwound in reverse order.
- 4
Deep recursion can cause stack overflow.
- 5
Many recursive algorithms can be converted into iterative solutions.
Scenario Questions
0-2 years experience
- 1Write a function to compute the nth Fibonacci number using recursion. How does the call stack evolve with each call?
- 2Given a binary tree node class, how would you implement a recursive in‑order traversal, and what does the stack look like during the traversal?
2-5 years experience
- 1We added a recursive parser for nested JSON objects, but it crashes with a stack overflow on deep inputs. How would you diagnose and fix the issue?
- 2We need to refactor a recursive depth‑first search into an iterative version for performance. Walk me through the trade‑offs and the steps you’d take.
5-8 years experience
- 1Design a service that processes hierarchical data (e.g., an org chart) and computes aggregates recursively. How would you ensure it scales and avoids stack overflow in a distributed setting?
- 2Explain how you would apply tail‑call optimization or a trampoline technique in a language without native TCO to handle very deep recursion.
8+ years experience
- 1Our legacy system uses deep recursive algorithms for query planning, leading to high memory usage. How would you plan a migration to iterative or streaming approaches while keeping correctness across multiple teams?
- 2When designing a language runtime, what considerations around the call stack and recursion support influence the choice between a fixed‑size stack and a segmented or growable stack?
Follow-up Questions
- What happens if the base case is never reached?
- How does tail recursion affect stack usage compared to regular recursion?
- Can you estimate the recursion depth that would cause a stack overflow on a typical JVM?