Factorial
The "hello world" of recursion: n! = n × (n−1)!. Watch each call wait on the stack until the base case returns, then the results multiply on the way back up.
- Category
- Recursion
- Time complexity
- O(n)
- Space complexity
- O(n) stack
Pseudocode
if n ≤ 1: return 1 push frame: n × factorial(n−1) unwind: multiply on return result bubbles to the top
Reference implementation
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)