Recursive factorial
- Algorithms course
- Beginner
- Lesson 46/80
- 4 min
Write a recursive factorial function.
Iterative solution
Factorial can also be computed with a loop: multiply numbers from 1 to n. This uses less memory than recursion.
The iterative solution requires O(n) time and O(1) memory. The recursive solution requires O(n) time and O(n) memory (stack).
Recursive vs iterative
Recursive factorial is more readable but each call uses stack space. The iterative solution is more efficient but less elegant.
For small n, both methods are fast. For large n, iterative is preferred because there is no stack overflow risk.
Practice Iterative factorial
Write factorial_iter(n). Multiply from 1 to n with a loop. Print 120 with print(factorial_iter(5)).
Starter code
def factorial_iter(n):
# Factorial with loopSample solution
def factorial_iter(n):
# Factorial with loop
result = 1
for i in range(1, n + 1):
result = result * i
return result
print(factorial_iter(5))Expected output
120
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Iterative product
To accumulate the result, start with ____ = 1.To accumulate the result, start with result = 1.Explanation: result is right.
2 Recursive factorial: match the terms
| Term | Meaning |
|---|---|
Recursive |
Uses stack |
Iterative |
O(1) memory |
0! = 1 |
Base |
n! = n*(n-1)! |
Recursive |
3 How much memory does iterative factorial use?
- O(1) Correct answer
- O(n^2)
- O(n)
- O(2^n)
Explanation: Iterative factorial uses O(1) memory.