- Home
- /
- CS Thinking
- /
- Mistakes
- /
- Recursion
Common Mistakes in Recursion
Recursion solves problems by breaking them into smaller versions of themselves. These mistakes lead to infinite loops or wrong results.
Why these errors repeat
Most recursion errors are not careless slips. They happen when a shortcut feels close enough to the real idea that it seems safe to reuse. That is why patterns like leaving out the base case or writing a base case the calls never reach keep showing up even after more practice.
Once you can name the temptation behind a mistake, it becomes much easier to notice it in homework, tests and worked examples.
Quick checklist
- Leaving out the base case
- Writing a base case the calls never reach
- Making a recursive call that does not shrink the problem
- Confusing recursion with iteration
- Forgetting stack growth
- Assuming recursion is "magic"
Where people get stuck
- 1.
Leaving out the base case
Every recursive function needs a case it answers directly. For factorial, return 1 when n is 0; returning 0 there makes every result 0, and leaving it out recurses until the stack overflows.
- 2.
Writing a base case the calls never reach
Check that every call moves toward the base case for every allowed input. If fact(n) stops only at n = 0, then fact(−1) counts down past 0 without ever reaching it, so reject negative input.
- 3.
Making a recursive call that does not shrink the problem
Each call must work on a smaller input, such as n − 1 or half the list. sum(list) should call sum on the list without its first item; calling sum(list) again never gets closer to the base case.
- 4.
Confusing recursion with iteration
A loop repeats steps inside one call; recursion solves a smaller copy of the problem and builds on its answer. Since n! = n × (n − 1)!, fact(n) returns n × fact(n − 1).
- 5.
Forgetting stack growth
Each call waits on the call stack until the calls below it return, so fact(10000) holds 10,000 frames at once and can overflow. For very deep inputs, use a loop instead.
- 6.
Assuming recursion is "magic"
Trace a small case by hand: fact(3) = 3 × fact(2) = 3 × 2 × fact(1) = 3 × 2 × 1 × fact(0) = 6. Trust the pattern once the base case and the smaller step are both correct.
Stuck?
Understanding the core concept helps you avoid these mistakes naturally.
See the core concept: RecursionSelf-check before you submit
- Before you move on, check whether you are leaving out the base case.
- Before you move on, check whether you are writing a base case the calls never reach.
- Before you move on, check whether you are making a recursive call that does not shrink the problem.