Definition
n! & 0!
Product 1…n; empty product gives 0! = 1.
Find Factorial in C
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 C solutions, unsigned long long overflow limits, a live preview, worked C examples, edge cases, and complexity.
Recurrence
n·(n-1)!
Classic recursive interview form.
Iterative
O(1) space
Loop multiply avoids call-stack depth growth.
Overflow
n ≤ 20
unsigned long long holds exact n! only through 20!.
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 C program also validates n ≥ 0, watches unsigned long long overflow, and prefers loops for large n.
Why it matters?
It is the classic interview problem for base cases, recurrence vs loops, stack depth, and fixed-width integer overflow in C.
Key Highlights
0! = 1
Empty product — say it clearly in interviews.
Recurrence
n! = n · (n-1)! for n ≥ 1.
Loop Safer
Iteration avoids stack-depth growth.
Cap at 20!
Exact unsigned long long stops at n = 20.
In short: for n ≥ 0, multiply 1 through n (or return 1 when n is 0 or 1) — and bound n before silent unsigned wrap.
Foundation
📝 Problem & Approach
Given a nonnegative integer n, compute n! within a chosen numeric type.
c
/* 0! = 1
* 5! = 5 * 4 * 3 * 2 * 1 = 120
* 6! = 6 * 5! = 720 */Inputs & Outputs
| Item | Type | Description |
|---|---|---|
n | int | Nonnegative integer (reject negatives). |
| Return / print | unsigned long long / text | Exact value of n! when it fits (typically n ≤ 20). |
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 |
| Overflow-aware | Reject n > 20 for ull | Avoids silent wrap |
Cheat Sheet
⚡ Quick Reference
| Goal | Pattern |
|---|---|
| Base case | if (n <= 1) return 1; |
| Recurrence | return (unsigned long long)n * factorial(n - 1); |
| Loop | for (i = 2; i <= n; ++i) r *= (unsigned long long)i; |
printf("%llu\n", result); | |
| Classic values | 0! = 1, 5! = 120, 20! = 2432902008176640000 |
| Reject | n < 0 or n > 20 for exact ull |
Compare
📋 Recursive vs Iterative vs Overflow Guard
Three angles interviewers expect — clarity, stack, and integer width.
Recursive
n * f(n-1)Teaches base case + recurrence
Iterative
loop *= iSafer stack for larger n
Bound n
n <= 20Keeps results exact in ull
Interview tip
both + overflowShow recursion, then loop + limits
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.
Overflow drills
C forces you to discuss silent wrap vs big integers.
Key benefit: one short function that forces clear thinking about base cases, stack space, and type width.
Interactive
🔮 Live Preview
Exact factorial for 0 ≤ n ≤ 20 (matches a typical unsigned long long ceiling before wrap).
Hands-On
Examples Gallery
Three complete C programs — recursive, iterative, and a small table of known values with overflow guards. Click View Output to reveal sample console results.
📚 Getting Started
Base case + recurrence for interview explanations.
Example 1 — Recursive Factorial
Classic recursive style with negative and overflow checks for unsigned long long.
c
#include <stdio.h>
#define FACT_MAX_ULL 20
unsigned long long calculate_factorial(int num) {
if (num == 0 || num == 1) {
return 1u;
}
return (unsigned long long)num * calculate_factorial(num - 1);
}
int main(void) {
int number = 5;
if (number < 0) {
printf("Factorial is not defined for negative integers here.\n");
return 0;
}
if (number > FACT_MAX_ULL) {
printf("n too large for exact unsigned long long in this demo (max %d).\n", FACT_MAX_ULL);
return 0;
}
unsigned long long result = calculate_factorial(number);
printf("Factorial of %d is: %llu\n", number, result);
return 0;
}How It Works
Each call shrinks num until the base case; products bubble back up. Cast num before multiplying so intermediate products stay in unsigned long long. Stack depth is O(n).
⚡ Iterative Style
Same numeric result with O(1) auxiliary space.
Example 2 — Iterative Factorial
No call-stack depth proportional to n; multiply factors from 2 to n.
c
#include <stdio.h>
#define FACT_MAX_ULL 20
unsigned long long factorial_iter(int n) {
unsigned long long r = 1u;
int i;
for (i = 2; i <= n; ++i) {
r *= (unsigned long long)i;
}
return r;
}
int main(void) {
int number = 5;
if (number < 0) {
printf("Factorial is not defined for negative integers here.\n");
return 0;
}
if (number > FACT_MAX_ULL) {
printf("n too large for exact unsigned long long in this demo (max %d).\n", FACT_MAX_ULL);
return 0;
}
printf("Factorial of %d is: %llu\n", number, factorial_iter(number));
return 0;
}How It Works
The loop multiplies 1 by every integer from 2 through n. For n in {0, 1}, the loop body never runs and r stays 1.
📊 Known Values
Spot-check classics that fit in unsigned long long.
Example 3 — Print a Small Factorial Table
Handy for verifying 0!, 1!, 5!, 10!, and the 20! ceiling.
c
#include <stdio.h>
unsigned long long factorial_iter(int n) {
unsigned long long r = 1u;
int i;
for (i = 2; i <= n; ++i) {
r *= (unsigned long long)i;
}
return r;
}
int main(void) {
int values[] = {0, 1, 5, 10, 20};
int i;
for (i = 0; i < 5; ++i) {
int n = values[i];
printf("%d! = %llu\n", n, factorial_iter(n));
}
return 0;
}How It Works
Reuse the iterative helper and print a short checklist of values. In interviews, knowing 5! = 120 and that 21! overflows 64-bit unsigned is a strong follow-up answer.
🧠 How the Algorithm Computes
1
Validate
Reject n < 0; optionally reject n > 20 for exact ull.
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 when the type can hold it.
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 factorial(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” and “21! overflows 64-bit unsigned” before coding — interviewers listen for both.
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 on the stack.
3. Famous Test Cases
0, 1, 5, and 20 are easy to verify by hand.
4. Overflow Is Discussable
C lets you demonstrate awareness of silent unsigned wrap.
Pro Tip: show recursion for the whiteboard, then say you would ship the iterative version with an n ≤ 20 guard (or a big-int library).
Usage Tips
Small habits that keep factorial solutions interview-ready in C.
1. State 0! = 1
Call out the empty-product base case first.
2. Validate Negatives
Print an error and return for n < 0.
3. Prefer Loops for Larger n
Avoid deep call stacks even when the type still fits.
4. Cast Before Multiply
Promote to
unsigned long longso products do not truncate early.5. Spot-Check 5 and 0
120 and 1 catch base-case mistakes fast.
Pro Tip: unsigned overflow wraps silently in C — bound n or check before multiply, never assume wrap is “just wrong.”
Common Pitfalls
Mistakes that commonly break factorial solutions in C.
1. Forgetting 0!
Returning 0 or erroring 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 reject early.
3. Ignoring Overflow
21! exceeds 264−1; unsigned wrap is silent.
→ Cap at n ≤ 20 or use big-integer libraries.
4. Using
intfor the Result13! already exceeds 32-bit signed
int.→ Prefer
unsigned long longfor small exact factorials.5. Deep Recursion Only
Even when n fits, stack frames may not.
→ Prefer iterative for moderately large n.
Edge Cases
Unsigned overflow is silent in C; always bound n or check products before they wrap.
Negative
n < 0
Not defined in standard factorial; reject instead of recursing.
Zero / one
0! and 1!
Both equal 1 — your base case must cover them.
Overflow
21! and beyond
Exceeds 264−1; widen to big integers or change the problem.
Stack
Deep recursion
Very large n can overflow the call stack before the integer type does.
Types
int result
13! already exceeds 32-bit int; prefer wide unsigned.
Printf
%llu
Match the conversion specifier to unsigned long long.
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
- 20! = 2432902008176640000
2. Match both styles
- Recursive vs iterative
- Assert identical results for n ≤ 20
3. Reject negatives
- Print an error for n < 0
- Never recurse on negatives
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 saves stack depth.
- Watch-outs: negatives undefined;
unsigned long longcaps near 20!; silent unsigned wrap. - 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 to ship, and bound n for exact ull.
Analysis
⏱️ Time and Space Complexity
| Version | Time | Extra space |
|---|---|---|
| Recursive | O(n) multiplications | O(n) call frames |
| Iterative | O(n) multiplications | O(1) |
Both approaches use Θ(n) arithmetic operations for exact n!; only the hidden stack differs. Result bit-width 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 when n grows, validate negatives, and keep exact unsigned long long results within n ≤ 20.
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 stack depth vs O(1) loop space plus silent unsigned wrap.
Pro Tips
💡 Best Practices
✅ Do
- State 0! = 1 up front
- Validate n ≥ 0
- Show recursive and iterative
- Use
unsigned long long+%llu - Mention the n ≤ 20 exact ceiling
❌ Don’t
- Return 0 for 0!
- Recurse on negatives
- Ignore silent unsigned wrap
- Store big results in 32-bit
int - Assume recursion is fine for huge n
Summary
Key Takeaways
Knowledge Unlocked
Five things to remember about factorial
Compute n! the interview-friendly way in C.
5
Core concepts 01
Rule
0! = 1
Definition 02
Recur
n·(n-1)!
Theory 03
Iterate
O(1) space
Practice 04
Guard
n ≥ 0, n ≤ 20
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 (empty product).
Both 0! and 1! equal 1. Those cases terminate the recurrence n! = n * (n-1)! without further calls.
On typical 64-bit platforms, unsigned long long holds values up to 2^64-1. Since 21! exceeds that, this type can store n! exactly only for n <= 20 in the usual range.
Both run O(n) multiplications. Recursion uses O(n) call stack space; a simple loop uses O(1) extra space and avoids stack overflow for moderately large n (still subject to numeric overflow).
Factorial is not defined for negative integers in the standard combinatorial sense. Programs should validate n >= 0 before computing.
Computing n! with n multiplications costs O(n) time. Space is O(n) for naive recursion depth or O(1) for an iterative loop excluding the result width.
printf needs a matching conversion specifier. For unsigned long long, %llu is the portable choice in standard C.
It is the empty product, and it makes the recurrence n! = n*(n-1)! work for n = 1.
Did you Know? 🔊
Stirling's approximation describes how fast n! grows: asymptotically n! ∼ √(2πn) · (n/e)n. It is standard in analysis even when the exact integer no longer fits in fixed-width types.
Continue to Fibonacci Series
Learn iterative and recursive ways to print the Fibonacci sequence.
About the author
8 people found this page helpful