easyNumber ProblemsJava

Find the Factorial of a Number Using Recursion

Compute the factorial of a non-negative integer using recursion.

Quick Answer

Define factorial(n) as n * factorial(n - 1), with a base case that returns 1 when n is 0 or 1. Each call reduces n by one until it reaches the base case, then the multiplications unwind back up the call stack to produce n!.

Problem Statement

The factorial of n, written n!, is the product of all integers from 1 to n, with 0! = 1. It has a natural recursive definition: n! = n * (n - 1)!, bottoming out at 0! = 1.

Given a non-negative integer n, compute n! using recursion: a method that calls itself with a smaller argument until it reaches the base case. Return the result as a long.

Input: A single non-negative integer n.

Output: The factorial n! as a long.

Examples

Example 1
Input:  6
Output: 720

6! = 6 * 5! = 6 * 120 = 720.

Example 2
Input:  1
Output: 1

1 hits the base case directly and returns 1.

Constraints

  • 0 <= n <= 20 keeps the result within long range
  • Solve it recursively with a clear base case

Think Before You Code

Reveal the questions to ask yourself first
  • What is the base case that stops the recursion from going forever?
  • How does each call make the problem smaller?
  • In what order do the multiplications actually happen as the calls unwind?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
Every recursion needs a base case: return 1 when n is 0 or 1.
Hint 2
The recursive step is simply `return n * factorial(n - 1)`.
Hint 3
Trace the calls: factorial(3) waits for factorial(2), which waits for factorial(1); results multiply as the stack unwinds.

Approach

Reveal the step-by-step approach

Express the factorial in terms of a smaller factorial.

  1. Base case: if n <= 1, return 1.
  2. Recursive case: return n * factorial(n - 1).

Each call peels off one factor and delegates the rest to a smaller call. When the base case returns 1, the pending multiplications resolve from the bottom up.

Dry Run

Walk through the example step by step

Computing factorial(6) via the call stack:

call         | returns
-------------+-----------------------
factorial(6) | 6 * factorial(5)
factorial(5) | 5 * factorial(4)
factorial(4) | 4 * factorial(3)
factorial(3) | 3 * factorial(2)
factorial(2) | 2 * factorial(1)
factorial(1) | 1  (base case)

unwind: 2*1=2, 3*2=6, 4*6=24, 5*24=120, 6*120=720

Final result: 720

Solution

Reveal the full Java solution
public class FactorialRecursion {
    public static long factorial(int n) {
        if (n <= 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(factorial(6)); // 720
        System.out.println(factorial(1)); // 1
    }
}

The base case n <= 1 covers both 0! and 1! and guarantees termination. Because n is an int but the method returns long, the multiplication n * factorial(n - 1) is promoted to long arithmetic, so the growing product does not overflow as early as it would with an int return type.

Time: O(n) — one call per value from n down to 1Space: O(n) for the recursion call stack

Common Mistakes

  • Forgetting the base case, causing infinite recursion and a StackOverflowError.
  • Returning int from the method, so the product overflows before long promotion helps.

Edge Cases to Test

  • factorial(0) returns 1 because it hits the base case immediately.
  • Very large n risks a StackOverflowError from too many nested calls.

Interview Follow-Ups

  • How would you rewrite this iteratively to avoid the call-stack cost?
  • How would you make the recursion tail-recursive, and does Java optimize that?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us