Watch out for these common recursion mistakes:
Missing base case:
def broken(n):
return n + broken(n - 1) # Never stops!
Base case never reached:
def broken(n):
if n == 0:
return 0
return broken(n + 1) # Goes wrong direction!
Not returning the recursive result:
def broken(n):
if n == 0:
return 1
factorial(n - 1) # Missing return!
return n
Off-by-one in base case:
def count(n):
if n == 0: # Should be n < 10 for digit count
return 0
return 1 + count(n // 10)
Always trace a few examples by hand.