Factorial of a given number
Easyn times the factorial below it
Problem
Return N! = 1 x 2 x ... x N using recursion.
n! = n times (n-1)! — keep shrinking until you hit the base case 0! = 1.
The idea
n! is n × (n-1)!, bottoming out at 0! = 1. The structure is identical to the sum; only the combining operation changes, which is worth seeing explicitly.
The trick
- 0! = 1, not 0 — the multiplicative identity.
- Factorials overflow 64-bit integers past 20.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
5
0
Step 1 of 2. Here's the example — n = 5 Values: 5.
1/2
Optimal
timeO(n)spaceO(n)
1f(n):2 if n<=1: return 13 return n * f(n-1)Input
- array
- [5]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- n = 5
- Output:
- 120
- Explanation:
- 5 x 4 x 3 x 2 x 1 = 120.
Example 2
- Input:
- n = 0
- Output:
- 1
- Explanation:
- 0! is defined as 1.
Example 3
- Input:
- n = 3
- Output:
- 6
- Explanation:
- 3 x 2 x 1 = 6.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.