The recursive case breaks the problem into a smaller version of itself. You assume the smaller problem will be solved correctly, then use that result.
def factorial(n):
if n == 0: # Base case
return 1
return n * factorial(n - 1) # Recursive case
When computing factorial(5):
- Assume
factorial(4)returns the correct answer () - Multiply:
This "trust the recursion" mindset is key. Don't trace every call mentally. Focus on:
Does my base case return the right answer?
If the recursive call works, does my combination step produce the right result?