Think together · Start with a little story
The robot needs to label four boxes. It labels one first, and the remaining three can be handled in the same way. How can you tell whether this is a useful way to split the task?
Lay out the process
- Original taskHandle 4 items
- Do one small stepHandle 1 item
- Remaining taskHandle 3 items
- Simplest task0 items means stop
A recursive step must preserve the problem type while reducing its size.
The small step and the work on what remains must together solve the original problem exactly—without missing or repeating anything.
01What are “smaller problems inside a problem”?
Some problems can naturally be described this way:
“If I already know how to solve a smaller problem of the same kind, I only need to do a little more work to solve this one.”
That is exactly the kind of structure recursion handles well.
02Step 1: Define what the function means
For example:
int sumTo(int n)First, define its meaning:
Return the sum of the integers from 1 through n.
When the function's meaning is clear, the recursive relationship is easier to reason about.
03Step 2: Find the simplest problem
When n == 0:
if (n == 0) {
return 0;
}04Step 3: Make the current problem smaller
If you know that sumTo(n - 1) gives you the sum of the first n-1 numbers, then:
return n + sumTo(n - 1);05Why can you “trust” the next call?
The function's definition is already clear: sumTo(k) is responsible for finding the sum from 1 through k.
When designing recursion, you do not need to unfold every deeper detail in the current call. Just make sure that:
The function has a clear meaning
Every call performs the same kind of task.
The problem gets smaller
The next call handles a simpler problem.
The process can stop
It eventually reaches the base case.
06When should you avoid forcing recursion?
If a problem has no natural smaller problem of the same kind, forcing recursion can make the code more complicated.
For example, a loop is usually clearer for simply printing the numbers from 1 to 100.
What have you learned?
- Recursion suits tasks that can shrink into smaller problems of the same kind.
- Before writing a recursive function, define its responsibility clearly.
- Then find the base case and a way to reduce the problem.
- Trusting that a smaller problem can be solved is an important part of recursive thinking.
- If a problem has no natural recursive structure, you do not have to force one.
Next: How Can Recursion Solve a Maze?
Your turn to try
After labeling the first box, what could go wrong if the next call starts with that same first box?
Ready? Open to see the explanation
The same box might be processed repeatedly, so the remaining task would not get smaller. Update the position and the number of boxes left.