AI Hints
DSA in Python · Lesson 42 of 132

Base Cases

And when recursion goes wrong.

⏱ 2 min read▶ Video at 48:32🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

The most common recursion bug is a missing or wrong base case. The function calls itself forever, the call stack fills up, and Python stops with an error. Let's see it happen, so you'll recognise it.

Base Cases
From the video: Base Cases
  • Missing base case
  • The stack fills up
  • Python stops with an error

Forgetting the base case

This version of countdown has no base case. It just keeps calling itself, with smaller and smaller numbers, into the negatives. Run it. After about a thousand calls, Python gives up with a recursion error. Maximum recursion depth exceeded.

no_base.pypython
def countdown(n):
    print(n, end=" ") if n > 997 else None
    countdown(n - 1)

try:
    countdown(1000)
except RecursionError as e:
    print("\nRecursionError:", e)
Output
1000 999 998
RecursionError: maximum recursion depth exceeded

Writing good base cases

Always write the base case first, before the recursive call. Make sure every call moves closer to it, usually by making the input smaller. Check the edge cases, like zero, one, or an empty list. And if the depth could be huge, like a million, use a loop instead.

keyvalue
Base case firstat the top
Move closersmaller input every call
Edge cases0, 1, empty
Very deep?use a loop

Summary

A missing base case causes a recursion error. Write the base case first, and make every call move towards it. Next, recursion practice.

Key takeaways
  • Base case first
  • Always get smaller
  • RecursionError = no way out
Next up: Recursion Practice — sum, power and digits