Loading…

easyBasicsFrequently asked

Factorial (Recursion)

Basics · 6 min

Given a non-negative integer n, compute n! (n factorial) recursively.

In plain English

Define factorial in terms of a smaller factorial: n! = n · (n-1)!, with 0! = 1 as the base case.

Examples

Example 1

Input: n = 5
Output: 120
Note: 5·4·3·2·1.

Example 2

Input: n = 0
Output: 1
Note: Base case.

Example 3

Input: n = 1
Output: 1
Note: 1! = 1.

Constraints

0 ≤ n ≤ 20 (fits in a 64-bit long)

Clarifying questions1First question: Recursion required, or is iteration fine?Explore questions

Q1.Recursion required, or is iteration fine?
I'll show recursion as asked; iteration avoids stack depth.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Base case: `n <= 1` returns 1. Recursive case: return `n * factorial(n-1)`. Use `long` since factorials grow fast.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you structure a recursion with a correct base case and shrinking step.

Where candidates slip

Omitting or mis-placing the base case; int overflow.

How to stand out

Note iteration avoids the O(n) stack, and quote the long overflow limit (20!).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Linear recursion

TimeO(n)SpaceO(n) call stack

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Express n! in terms of a smaller factorial.

2Hint 2Explore hint

What input stops the recursion?

3Hint 3Explore hint

Each call adds a stack frame — what's the space cost?

A · Core idea

The textbook first recursion: n! = n · (n−1)!, with 0! = 1 (and 1! = 1) as the base case that stops the descent. Every recursion needs exactly these two pieces — a base case and a recursive case that shrinks the problem.

Why the base case is non-negotiable. Without if (n <= 1) return 1, the calls descend forever (n, n−1, …, into negatives), overflowing the call stack. The base case is what guarantees termination.

How the call stack unwinds. factorial(5) waits for factorial(4), which waits for factorial(3), … down to factorial(1)=1; then the stack unwinds multiplying back up: 1→2→6→24→120. Each frame uses stack space, so this is O(n) stack — iteration avoids that.

Overflow. Use long; 20! is the largest factorial that fits in signed 64-bit, and 13! already overflows int.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4

call

4·f(3)·…·f(1)

Statestack builds

Final result24

C · Code with teaching comments

solution.javaJava

Linear recursion — optimal

2 teaching notes

1
public long factorial(int n) {
2
    // Base case stops the recursion.
3
    if (n <= 1) return 1;
4
    // Recursive case shrinks n by one.
5
    return (long) n * factorial(n - 1);
6
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.6 lines

D · Why it works and complexityO(n) timeO(n) call stack spaceOpen the invariant and proofExplore the proof

20! is the largest factorial fitting in a signed 64-bit long; beyond that you need BigInteger.

ComplexityO(n) time, O(n) call stack space — n nested calls, one multiply each, with an O(n)-deep call stack.

E · Edge cases and pitfalls5n = 0 — Base case returns 1 (0! = 1).Explore edge cases

Edge cases handled

n = 0Base case returns 1 (0! = 1).
n = 1Base case returns 1.
n = 21Overflows even long.

Pitfalls

Missing base case → infinite recursion / stack overflow.
Using int and overflowing past 12!.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long factorial(int n) { if (n <= 1) return 1; return (long) n * factorial(n - 1); }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

No base case

Without a stopping condition the function recurses past 0 into negatives until the stack overflows.

Explore the code comparison

Don't write this

long f(int n){ return n * f(n-1); }       // never stops

Write this instead

long f(int n){ if (n <= 1) return 1; return n * f(n-1); }

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Base case + shrink

Code pattern to memorize

f(n) = n<=1 ? 1 : n * f(n-1)

Rules to remember

10!/1! = 1.
2n! = n·(n-1)!.
3Use long.

Use this pattern when

Teaching recursion
Naturally self-similar products

Choose another pattern when

Large n — recursion risks stack overflow; iterate

Interview takeaway

Every recursion = a base case plus a smaller subproblem.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Base case + shrink. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern

easyBasicsFrequently asked

Factorial (Recursion)

Basics · 6 min

Given a non-negative integer n, compute n! (n factorial) recursively.

In plain English

Define factorial in terms of a smaller factorial: n! = n · (n-1)!, with 0! = 1 as the base case.

Examples

Example 1

Input: n = 5
Output: 120
Note: 5·4·3·2·1.

Example 2

Input: n = 0
Output: 1
Note: Base case.

Example 3

Input: n = 1
Output: 1
Note: 1! = 1.

Constraints

0 ≤ n ≤ 20 (fits in a 64-bit long)

Clarifying questions1First question: Recursion required, or is iteration fine?Explore questions

Q1.Recursion required, or is iteration fine?
I'll show recursion as asked; iteration avoids stack depth.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Base case: `n <= 1` returns 1. Recursive case: return `n * factorial(n-1)`. Use `long` since factorials grow fast.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you structure a recursion with a correct base case and shrinking step.

Where candidates slip

Omitting or mis-placing the base case; int overflow.

How to stand out

Note iteration avoids the O(n) stack, and quote the long overflow limit (20!).

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Linear recursion

TimeO(n)SpaceO(n) call stack

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Express n! in terms of a smaller factorial.

2Hint 2Explore hint

What input stops the recursion?

3Hint 3Explore hint

Each call adds a stack frame — what's the space cost?

A · Core idea

Overflow. Use long; 20! is the largest factorial that fits in signed 64-bit, and 13! already overflows int.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4

call

4·f(3)·…·f(1)

Statestack builds

Final result24

C · Code with teaching comments

solution.javaJava

Linear recursion — optimal

2 teaching notes

1
public long factorial(int n) {
2
    // Base case stops the recursion.
3
    if (n <= 1) return 1;
4
    // Recursive case shrinks n by one.
5
    return (long) n * factorial(n - 1);
6
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.6 lines

D · Why it works and complexityO(n) timeO(n) call stack spaceOpen the invariant and proofExplore the proof

20! is the largest factorial fitting in a signed 64-bit long; beyond that you need BigInteger.

ComplexityO(n) time, O(n) call stack space — n nested calls, one multiply each, with an O(n)-deep call stack.

E · Edge cases and pitfalls5n = 0 — Base case returns 1 (0! = 1).Explore edge cases

Edge cases handled

n = 0Base case returns 1 (0! = 1).
n = 1Base case returns 1.
n = 21Overflows even long.

Pitfalls

Missing base case → infinite recursion / stack overflow.
Using int and overflowing past 12!.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic long factorial(int n) { if (n <= 1) return 1; return (long) n * factorial(n - 1); }Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

No base case

Without a stopping condition the function recurses past 0 into negatives until the stack overflows.

Explore the code comparison

Don't write this

long f(int n){ return n * f(n-1); }       // never stops

Write this instead

long f(int n){ if (n <= 1) return 1; return n * f(n-1); }

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Base case + shrink

Code pattern to memorize

f(n) = n<=1 ? 1 : n * f(n-1)

Rules to remember

10!/1! = 1.
2n! = n·(n-1)!.
3Use long.

Use this pattern when

Teaching recursion
Naturally self-similar products

Choose another pattern when

Large n — recursion risks stack overflow; iterate

Interview takeaway

Every recursion = a base case plus a smaller subproblem.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Base case + shrink. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Same pattern