What is Recursion? How does it relate to the Call Stack?

Difficulty: 5/10

base case, stack overflow, tail recursion

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.

javascript

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

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?

Follow-up Questions