Definition
n! & 0!
Product 1…n; empty product gives 0! = 1.
Find Factorial in Java
Overview
What You’ll Learn
Factorial n! is the product of integers from 1 through n, with 0! = 1. This tutorial covers recursive and iterative solutions, BigInteger, a live preview, worked Java examples, edge cases, and complexity.
Recurrence
n·(n-1)!
Classic recursive interview form.
Iterative
O(1) space
Loop multiply avoids recursion-depth limits.
BigInteger
Builtin
Best for real code after you can write it yourself.
Live Preview
n ≤ 20
Exact factorials in the browser for small n.
O(n)
Multiplies
Both styles use Θ(n) multiplications.
Introduction
Factorial for an integer n ≥ 0 is the product of every integer from 1 through n. By definition, 0! = 1 (the empty product). Example: 5! = 5 × 4 × 3 × 2 × 1 = 120.
Factorials count permutations: n! is the number of ways to order n distinct objects. Values grow extremely fast — a correct small-n program is easy; a robust one also validates n ≥ 0 and prefers loops for large n.
Why it matters?
It is the classic interview problem for base cases, recurrence vs loops, and recursion-depth tradeoffs.
Key Highlights
0! = 1
Empty product — say it clearly in interviews.
Recurrence
n! = n · (n-1)! for n ≥ 1.
Loop Safer
Iteration avoids recursion-depth errors.
No Negatives
Reject n < 0 — factorial is undefined there.
In short: for n ≥ 0, multiply 1 through n (or return 1 when n is 0 or 1).
Foundation
📝 Problem & Approach
Given a nonnegative integer n, compute n!.
java
// 0! = 1
// 5! = 5 * 4 * 3 * 2 * 1 = 120
// 6! = 6 * 5! = 720Inputs & Outputs
| Item | Type | Description |
|---|---|---|
n | int | Nonnegative integer (reject negatives). |
| Return / print | int / text | Exact value of n!. |
Minimal workflow
Pseudocode
function factorial(n): // assume n >= 0
if n <= 1:
return 1
return n * factorial(n - 1)Method comparison
| Method | Idea | Notes |
|---|---|---|
| Recursive | n * factorial(n-1) | Matches theory; O(n) stack |
| Iterative | Multiply 2…n in a loop | O(1) extra space |
BigInteger | BigInteger | Best for production code |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Base case | if (n <= 1) return 1; |
| Recurrence | return n * factorial(n - 1) |
| Loop | for (int i = 2; i <= n; i++) result *= i; |
| BigInteger | BigInteger multiply loop |
| Classic values | 0! = 1, 5! = 120, 10! = 3628800 |
| Reject | n < 0 → throw IllegalArgumentException |
Compare
📋 Recursive vs Iterative vs BigInteger
Three ways to compute n! — pick by clarity and constraints.
Recursive
n * f(n-1)Teaches base case + recurrence
Iterative
loop *= iSafer for large n (no stack depth)
BigInteger
BigIntegerOptimized and battle-tested
Interview tip
both + tradeoffShow recursion, then mention loop
Context
When This Problem Shows Up
Reach for factorial when products, permutations, or recursion drills appear.
Interview warm-ups
First recursion problem many candidates see.
Combinatorics
Permutations and combinations use n!.
Teaching recursion
Clear base case and single recursive call.
Before Fibonacci
Natural precursor to recursive sequences.
Not for negatives
Validate n ≥ 0 before computing.
Key benefit: one short function that forces clear thinking about base cases, space, and growth.
Interactive
🔮 Live Preview
Exact factorial for 0 ≤ n ≤ 20 (safe to display exactly in JavaScript).
Hands-On
Examples Gallery
Three complete Java programs — recursive, iterative, and BigInteger. Click View Output to reveal sample console results.
📚 Getting Started
Base case + recurrence for interview explanations.
Example 1 — Recursive Factorial
Classic recursive style with input validation.
java
public class Main {
static long factorialRecursive(int n) {
if (n < 0) {
throw new IllegalArgumentException("Factorial is not defined for negative integers.");
}
if (n <= 1) {
return 1;
}
return n * factorialRecursive(n - 1);
}
public static void main(String[] args) {
int number = 5;
long result = factorialRecursive(number);
System.out.println("Factorial of " + number + " is: " + result);
}
}How It Works
Each call reduces n until the base case 1, then products are built while returning. Stack depth is O(n), so prefer iteration for large n. Exact long results hold through 20!.
⚡ Iterative Style
Same numeric result with O(1) auxiliary space.
Example 2 — Iterative Factorial
No recursion-depth risk; multiply factors from 2 to n.
java
public class Main {
static long factorialIterative(int n) {
if (n < 0) {
throw new IllegalArgumentException("Factorial is not defined for negative integers.");
}
long result = 1;
for (int i = 2; i <= n; i++) {
result *= i;
}
return result;
}
public static void main(String[] args) {
int number = 5;
System.out.println("Factorial of " + number + " is: " + factorialIterative(number));
}
}How It Works
The loop multiplies 1 by every integer from 2 to n. For n in {0, 1}, the loop body never runs and result stays 1.
⚙️ BigInteger Style
Use fixed-width long (use BigInteger beyond 20!) when n may exceed 20.
Example 3 — BigInteger Factorial
Exact results beyond long — useful once 21! overflows.
java
import java.math.BigInteger;
public class Main {
static BigInteger factorialBig(int n) {
if (n < 0) {
throw new IllegalArgumentException("Factorial is not defined for negative integers.");
}
BigInteger result = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
result = result.multiply(BigInteger.valueOf(i));
}
return result;
}
public static void main(String[] args) {
int[] samples = {0, 1, 5, 10, 20, 25};
for (int n : samples) {
System.out.println(n + "! = " + factorialBig(n));
}
}
}How It Works
Prefer BigInteger when n may exceed 20. In interviews, write recursive or iterative with long first, then mention overflow and BigInteger.
🧠 How the Algorithm Computes
1
Validate
Reject n < 0; factorial is not defined for negatives.
Guard
2
Base case
If n ≤ 1, return 1 (covers 0! and 1!).
Stop
3
Recurrence or loop
Compute n * factorial(n-1), or multiply 2…n.
Product
=
n!
Exact product for nonnegative n.
Trace
🔎 Worked Walkthrough — n = 5
Trace the recursive expansion for the classic interview value.
| Call | Expression | Returns |
|---|---|---|
f(5) | 5 * f(4) | waits |
f(4) | 4 * f(3) | waits |
f(3) | 3 * f(2) | waits |
f(2) | 2 * f(1) | waits |
f(1) | base | 1 |
| unwind | 2*1 … 5*24 | 120 |
Final answer: 5! = 120.
Use Cases
Where factorial shows up beyond the interview prompt.
1. Interview Warm-Ups
Base case, recurrence, and loop tradeoffs.
Example: write factorialRecursive(n).
2. Permutations
n! counts orderings of n items.
Example: 5 books → 120 orders.
3. Combinations
C(n, k) uses factorials in the formula.
Example: n! / (k!(n-k)!).
4. Teaching Recursion
Single recursive call with a clear stop.
Example: chalkboard unwind of 5!.
5. Before Fibonacci
Warm-up for recursive series problems.
Example: next page in this chain.
6. Growth Awareness
Stirling’s approximation for large-n intuition.
Example: estimate digit growth of n!.
Pro Tip: say “0! = 1” before coding — interviewers listen for that base case.
Advantages
Why this pattern works well in interviews and classwork.
1. Clear Math
One recurrence and one base case tell the whole story.
2. Two Valid Styles
Recursion matches theory; loops scale better.
3. Famous Test Cases
0, 1, 5, and 20 are easy to verify.
4. Builtin Escape Hatch
BigIntegeris ready for production use.
Pro Tip: show recursion for the whiteboard, then say you would ship the iterative or builtin version.
Usage Tips
Small habits that keep factorial solutions interview-ready.
1. State 0! = 1
Call out the empty-product base case first.
2. Validate Negatives
Raise a clear error for n < 0.
3. Prefer Loops for Large n
Avoid recursion-depth exceptions.
4. Mention BigInteger
Show you know the production shortcut.
5. Spot-Check 5 and 0
120 and 1 catch base-case mistakes fast.
Pro Tip: Java long overflows after 20! — mention BigInteger for larger n.
Common Pitfalls
Mistakes that commonly break factorial solutions.
1. Forgetting 0!
Returning 0 or raising for n = 0.
→ Base case: n ≤ 1 returns 1.
2. Accepting Negatives Silently
Recursive calls never hit a base case for n < 0.
→ Validate and raise early.
3. Deep Recursion Only
Large n hits
StackOverflowError.→ Prefer iterative or
BigIntegerfor big n.4. Off-by-One in the Loop
Using
i < ndrops the last factor.→ Use
for (int i = 2; i <= n; i++).5. Worrying About C-style Overflow
Java
longoverflows after 20!; talk about BigInteger.→ Mention arbitrary-precision integers explicitly.
Edge Cases
Java long / BigInteger grow automatically, but recursion depth and runtime still matter.
Negative
n < 0
Not defined in standard factorial; reject with a clear error.
Zero / one
0! and 1!
Both equal 1 — your base case must cover them.
Recursion
Deep recursion
Large n can raise StackOverflowError; iterative code avoids this.
Huge output
Very large factorials
Numbers can be exact but enormous; printing and memory become expensive.
Validation
Non-integer input
Accept only integers for this interview problem.
Loop bound
i <= n
Inclusive end so the last factor is included.
Math
⚖️ Facts Worth Knowing
Handy follow-ups interviewers sometimes ask.
- Formal. 0! = 1 and n! = n · (n-1)! for n ≥ 1; equivalently ∏k=1n k.
- Permutations. n! counts ways to order n distinct objects.
- Growth. Each step multiplies by n, so values explode quickly.
- Stirling. Approximate growth with √(2πn) · (n/e)n.
Drill
🎯 Practice Problems
Try these variations to lock in the pattern.
1. Verify classics
- 0! = 1, 5! = 120
- 10! = 3628800
2. Match both styles
- Recursive vs iterative
- Assert identical results
3. Reject negatives
- Raise ValueError for n < 0
- Write a short unit test
4. Print the expansion
- Show 5 * 4 * 3 * 2 * 1
- Then the final value
Important
Notes
- Definition: 0! = 1 and n! = n·(n-1)! for n ≥ 1.
- Code: recursion matches theory; iteration avoids recursion-depth limits.
- Watch-outs: validate negatives; prefer loops for very large n.
- Both styles use Θ(n) multiplications; stack usage is the key difference.
Quick Takeaway: multiply 1 through n (with 0! = 1); use recursion to explain, loops (or BigInteger) to ship.
Analysis
⏱️ Time and Space Complexity
| Version | Time | Extra space |
|---|---|---|
| Recursive | O(n) multiplications | O(n) call frames |
| Iterative | O(n) multiplications | O(1) |
BigInteger | O(n) (implementation detail) | O(1) beyond result size |
Both approaches use Θ(n) arithmetic operations for exact n!; stack usage is the key difference. Result size grows with n and is excluded from the “extra space” column above.
🎉 Conclusion
Factorial multiplies 1 through n, with 0! = 1 by definition. Use recursion to match the recurrence, prefer an iterative loop (or BigInteger) when n grows, and always reject negatives.
Practice the three examples above, then continue to Fibonacci for the next classic sequence problem.
State the base case, explain O(n) time, and call out recursion-depth vs O(1) loop space.
Pro Tips
💡 Best Practices
✅ Do
- State 0! = 1 up front
- Validate n ≥ 0
- Show recursive and iterative
- Prefer loops for large n
- Mention
BigInteger
❌ Don’t
- Return 0 for 0!
- Recurse on negatives
- Ignore recursion-depth limits
- Use
i < nby mistake - Assume C-style int overflow
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about factorial
Compute n! the interview-friendly way.
5
Core concepts 01
Rule
0! = 1
Definition 02
Recur
n·(n-1)!
Theory 03
Iterate
O(1) space
Practice 04
Guard
n ≥ 0
Edge 05
Cost
Θ(n) ×
Analysis❓ Frequently Asked Questions
For a nonnegative integer n, n! is the product of all integers from 1 through n. By definition, 0! = 1.
Both 0! and 1! equal 1. Those cases terminate the recurrence n! = n * (n-1)!.
long can store exact factorial only up to 20!. 21! is larger than Long.MAX_VALUE. Use BigInteger for larger n.
Both run O(n) multiplications. Recursion uses O(n) call stack space and can hit recursion-depth limits; a loop uses O(1) extra space.
Factorial is not defined for negative integers in the standard combinatorial sense. Validate n >= 0 before computing.
Computing n! with n multiplications costs O(n) time. Space is O(n) for recursion depth or O(1) for iterative loop, excluding result size.
Yes when n may exceed 20. In interviews, write recursive or iterative with long first, then mention BigInteger for larger values.
It is the empty product, and it makes the recurrence n! = n*(n-1)! work for n = 1.
Did you Know? 🔊
Stirling's approximation is often used to estimate how fast n! grows: n! ∼ √(2πn) · (n/e)n.
Continue to Fibonacci Series
Learn iterative and recursive ways to print the Fibonacci sequence.
About the author
9 people found this page helpful