Start practising

Factorial of a number

Easy Recursion & Backtracking Basic Recursion

Factorial of a number is a easy recursion & backtracking problem solved with the basic recursion pattern. The best approach, iterative, runs in O(n) time and O(1) space. Below are 2 approaches in Java, from recursive up.

Problem

Compute n!, the product of all integers from 1 to n (with 0! = 1). This is the first problem for learning how recursion works: base case, recursive step and the call stack.

Examples

Example 1

Input
n = 5
Output
120
Why
5 × 4 × 3 × 2 × 1.

Example 2

Input
n = 0
Output
1

Constraints

  • 0 <= n <= 20 (20! still fits in a long)

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
RecursiveO(n)O(n)
IterativeO(n)O(1)

1Recursive

TimeO(n)
SpaceO(n)n frames on the call stack.

State the answer in terms of a smaller version of the same problem: fact(n) = n · fact(n - 1), with fact(0) = 1. Use it to picture the call stack: calls go down to the base case, and results are multiplied on the way back up.

  1. Base case: if n <= 1, return 1.
  2. Return n * fact(n - 1).
Java
class Solution {
    static long factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }
}

2Iterative

TimeO(n)
SpaceO(1)

Multiply 1 · 2 · ... · n in a loop. Same result, no call stack.

  1. r = 1; for i in 2..n: r *= i.
Java
class Solution {
    static long factorial(int n) {
        long r = 1;
        for (int i = 2; i <= n; i++) r *= i;
        return r;
    }
}

Edge cases to test

  • n = 0 (base case, 0! = 1)
  • Overflow beyond 20!

Hints

Hint 1

Every recursive function needs a base case that stops, and a step that moves toward it: n! = n × (n - 1)!.

FAQ

What is the best time complexity for Factorial of a number?

Iterative runs in O(n) time and O(1) extra space.

Which pattern does Factorial of a number use?

It is a recursion & backtracking problem that uses the basic recursion pattern. Other problems with the same pattern: Fibonacci Number, Binary Tree Inorder Traversal (Recursive), Basic Backtracking Template.

Is there a brute force solution for Factorial of a number?

Yes. Recursive takes O(n) time and O(n) space. State the answer in terms of a smaller version of the same problem: fact(n) = n · fact(n - 1), with fact(0) = 1.

Which edge cases should I test for Factorial of a number?

n = 0 (base case, 0! = 1); Overflow beyond 20!.