Complexity Analysis
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)What is the time and space complexity?
Work it out before scrolling down.
Time
O(n)
Space
O(n)
How to derive it
Makes n recursive calls (n, n-1, n-2, ..., 1), each doing O(1) work. Time is O(n). The call stack grows to depth n before unwinding, so space is O(n). This is the hidden cost of recursion — each frame stays on the stack.