Recursion Without Fear
Beginner · 16 min read · DSA Without Fear, The Toolkit
Trust the function: base case, smaller problem, combine. Recursion trees and the call stack.
Recursion is where many learners give up, usually because they try to trace every call in their head — and after three levels, nobody can. The trick that makes recursion easy is the opposite: don't trace it. Trust it.
The leap of faith
Writing a recursive function is answering three questions:
What actually happens: the call stack
You don't need to trace calls to write recursion, but it helps to see once what the computer does. Each call waits on a stack until the call it made returns:
Three shapes of recursion
Shrink by one each time: sum, reverse a linked list, length of a list. Depth n.
Return up vs pass down
Recursive functions move information in two directions:
The classic mistakes
Interview questions
- How do you convince yourself a recursive function is correct without tracing it?
- What is the space complexity of a recursive function that allocates nothing?
Further reading
Key takeaways
- Write recursion with three questions: base case, smaller problem, combine — and trust the recursive call.
- Recursion depth costs stack space; very deep recursion (around 100,000 calls) overflows in Java.
- Three shapes: linear, divide and conquer, branching. Branching with repeated calls is the signal for DP.
- Information is returned up (answers) or passed down (context); backtracking undoes its choices.
- Never compute the same recursive call twice in one step.