Recursion Guide for Beginners
Recursion can be one of the hardest topics to wrap your head around. That's why in this guide, we are breaking it down for total beginners.
The Gift Box Analogy
Imagine receiving a gift box. When you open it, instead of finding a gift, you find two smaller boxes inside. When you open the two smaller boxes, one has the gift, and the other has another smaller box inside.
In recursion, we encounter two types of boxes:
- Boxes with values inside (no more smaller boxes inside)
- Boxes containing more boxes (that need to be opened)
This translates to two key components of recursion:
Base Case
Boxes that contain values directly. These are our stopping points.
Recursive Case
Boxes that contain more boxes. These require further "unwrapping".
Fibonacci Example
To calculate each fibonacci number, we need the previous two fibonacci numbers (like we needed to open the boxes before we got to the gift).
- 0th Fibonacci number = 0
- 1st Fibonacci number = 1
We can represent this with the below formula:
F(n) = F(n-1) + F(n-2)
Base Case
F(1) = 1 and F(0) = 0 are our base cases. Without these, we can't do any calculations as there would be no stopping point (the gift would never be found).
In CS terms, this would lead to a stack overflow, because recursion uses the stack memory!
Recursive Case
F(n) = F(n-1) + F(n-2)
This is the part where the function calls itself. Every subproblem is treated as its own problem. The recursive case persists until we hit the base case.
E.g. To calculate F(5), we need F(4) + F(3), but to calculate F(4), we need to calculate F(3) + F(2). This goes on until we hit the base cases, after which the answers for the subproblems are added up to give us the final answer of F(5), which is 5.
Checklist for Solving Recursive Problems
- Figure out if you can break complex problems into similar smaller problems
- Identify clear base cases
- Ensure each recursive call moves toward a base case