Factorial (recursion)
Easy TimeO(n) SpaceO(n)
The factorial of a number is that number multiplied by every whole number below it, down to 1, so 5 factorial is 5 × 4 × 3 × 2 × 1 — 120. Given a number n, zero or greater, return n!. 0! is 1, not 0.
Examples
Example 1
- Input
- n = 5
- Output
1205 × 4 × 3 × 2 × 1 = 120.
Example 2
- Input
- n = 0
- Output
- An empty product is 1, so
10!is 1 and not 0.
The Code
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1);
}
factorial(5);Done
More like this
All recursion examples (13) →- Fibonacci The classic branching recursion — every call spawns two more.
- Tower of Hanoi Move a stack of disks by trusting the recursion for the rest.
- GCD (Euclid) Euclid’s algorithm — recursion that shrinks fast.
- Power Raise a number to a power one multiply at a time.
- Sum of digits Peel one digit off at a time with the modulo trick.
- Mutual recursion Two functions that call each other all the way down.