Choosing the base case
- Algorithms course
- Beginner
- Lesson 47/80
- 4 min
See how 0! = 1 base case works and the danger of a wrong one.
Base case selection
Factorial's base case is 0! = 1. This stops the recursion. A wrong base case causes infinite calls.
1! = 1 can also be used as a base case. Then the recursive step starts from 1 and one call is saved.
Complexity
Recursive factorial's complexity is O(n): each call decreases n by one, totaling n calls. Unlike Fibonacci, there is no repetition.
Memory complexity is also O(n) because each call adds a frame to the stack. The iterative solution uses O(1) memory.
Practice Factorial call
Write factorial_call(n). If n=1 return 1, else n * factorial_call(n-1). Print 24 with print(factorial_call(4)).
Starter code
def factorial_call(n):
# Call factorialSample solution
def factorial_call(n):
# Call factorial
if n == 1:
return 1
return n * factorial_call(n - 1)
print(factorial_call(4))Expected output
24
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Choosing the base case: match the terms
| Term | Meaning |
|---|---|
0! = 1 |
Base value |
n! = n*(n-1)! |
Recursive step |
Time |
O(n) time |
Memory |
O(n) stack |
2 What is the time complexity of recursive factorial?
- O(1)
- O(n^2)
- O(n) Correct answer
- O(2^n)
Explanation: O(n), n calls are made.
3 Memory complexity
Recursive factorial memory complexity is ____.Recursive factorial memory complexity is O(n).Explanation: O(n) is right.