Factorial of a number
Alright, factorial… what does factorial actually mean?
Factorial of a number n means I multiply all numbers from n down to 1.
So for example:
5! = 5 × 4 × 3 × 2 × 1
4! = 4 × 3 × 2 × 1
3! = 3 × 2 × 1
Now I want you to notice something very important here.
Look carefully:
5! = 5 × 4!
4! = 4 × 3!
3! = 3 × 2!
2! = 2 × 1!
So I can actually write a formula:
n! = n × (n-1)!
Now this is very interesting, because the factorial function is calling itself with a smaller number.
And whenever a function calls itself, that means recursion.
But wait — recursion always needs a stopping point, otherwise it will keep calling forever.
So when should we stop?
We know:
1! = 1
0! = 1
So these will be our base cases.
So now my thinking becomes:
If n is 0 or 1 → return 1
Otherwise → return n × factorial(n-1)
That’s it. That’s the whole recursion logic.
Let’s Dry Run (Very Important)
Let’s say I call:
factorial(5)
What happens?
factorial(5)
= 5 * factorial(4)
factorial(4)
= 4 * factorial(3)
factorial(3)
= 3 * factorial(2)
factorial(2)
= 2 * factorial(1)
factorial(1)
= 1 ← base case reached
Now values start returning back:
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
factorial(5) = 5 * 24 = 120
So recursion goes down first, then comes back up multiplying.
Very Important Concept
Recursion = function calls go down the stack, then results come back up.
Pseudocode (Thinking Steps)
factorial(n):
if n == 0 or n == 1:
return 1
else:
return n * factorial(n-1)
Edge Cases (Think Like Interviewer)
If I am in an interview, I should immediately think:
- What if n = 0? → return 1
- What if n = 1? → return 1
- What if n is negative? → factorial not defined
- What if n is very large? → stack overflow (too many recursive calls)
- What if factorial becomes very large? → integer overflow
Time Complexity (Think Properly)
How many function calls happen?
factorial(n)
factorial(n-1)
factorial(n-2)
...
factorial(1)
Total calls = n
So:
Time Complexity = O(n)
Space Complexity
Because recursion uses call stack, and we have n function calls in stack:
Space Complexity = O(n)
Very Important Interview Follow-up Questions
After this problem, interviewer usually asks:
- Write factorial using iteration
- Which one is better — recursion or iteration?
- What is tail recursion?
- What happens in stack memory during recursion?
We’ll cover these next.