Easy Base + Reduce Recursion
In plain English: Compute n factorial (n x (n-1) x ... x 1) using recursion.
The simplest recursion: reduce by one, multiply on the way back up. Base case 0! = 1 stops the chain.
Prompt
Compute n! recursively.
Try to write it from scratch before scrolling down.
Solution
def factorial(n):
if n <= 1:
return 1 # base case: 0! = 1! = 1
return n * factorial(n - 1) # multiply on unwind
# Iterative:
def factorial_iter(n):
result = 1
for i in range(2, n + 1):
result *= i # accumulate product bottom-up
return result
# Test: factorial(5) == 120