Recursion in Java: Base Case, Call Stack and Examples

printUpTo(5) prints 1 2 3 4 5. No loop, just a method that calls itself. That’s recursion.

Quick Answer

Recursion in Java is when a method calls itself to solve a smaller version of the same problem. Every recursive method needs a base case that stops the calls, and a recursive case that moves closer to it. Each call gets its own stack frame; without a reachable base case, the stack fills up and Java throws StackOverflowError.

Before you start: you should understand the call stack from Introduction to Methods and return values from Method Return Types.

What Is Recursion in Java?

Imagine a queue at a railway ticket counter. You want to know your position, but you can’t see the front. So you ask the person ahead, “What’s your position?” They ask the person ahead of them, and so on. The person at the front says “1” (that’s the base case). Each answer travels back down the line, everyone adds 1, and the answer reaches you.

That’s recursion: solve a big problem by trusting the answer to a smaller copy of it. Java has no special keyword for it; a method simply calls itself.

Base Case and Recursive Case

Every correct recursive method has two parts:

Factorial Using Recursion in Java

Output:

0! = 11! = 1
5! = 120
20! = 2432902008176640000

Three deliberate choices:

1. long, not int: int overflows at 13! (see Mistake 6).
2. A guard for negative input: without it, factorial(-1) would never reach 0 and would crash with StackOverflowError. With the guard it fails fast: IllegalArgumentException: n must be >= 0, got -1.
3. The base case is checked before the recursive call, so the method can stop.

How Recursion Works: The Call Stack

Each call to factorial gets a new stack frame holding its own n. Calls pile up until the base case, then unwind, each frame finishing its multiplication as it returns. This trace prints every step:

Output:

call factorial(4)  call factorial(3)
    call factorial(2)
      call factorial(1)
        call factorial(0)
        base case -> return 1
      return 1 * ... = 1
    return 2 * ... = 2
  return 3 * ... = 6
return 4 * ... = 24
Answer: 24

Work Before vs After the Call

Where you put the work decides the order of results:

Output:

4 3 2 1  <- printed on the way down1 2 3 4  <- printed on the way back up

What Happens Without a Base Case? (StackOverflowError)

Output:

 Exception in thread "main" java.lang.StackOverflowError	at NoBaseCase.dive(NoBaseCase.java:6)
	at NoBaseCase.dive(NoBaseCase.java:6)
	at NoBaseCase.dive(NoBaseCase.java:6)
	...

How Deep Can Recursion Go in Java?

There’s no fixed number. It depends on the thread stack size and on how big each frame is. Catching the error lets us count the calls (exception handling is covered in Introduction to Exception Handling). Measured on JDK 25, Linux x64, where the default stack size (ThreadStackSize) is 1024 KB:

Output may vary. Even identical runs differ, because the JIT compiler changes frame sizes while the program runs. Treat “a few thousand calls” as the safe range for plain recursion on default settings, and never design code that depends on going deeper. -Xss sets the stack size for new threads, but switching to a loop is usually the real fix.

More Recursion Examples in Java

Sum of Digits, Reverse a String and Fast Power

Output:

sumOfDigits(40517) = 17reverse("ExamAdda") = addAmaxE
power(2, 10) = 1024
power(3, 13) = 1594323

power halves the exponent each call, so power(3, 13) makes only about 5 calls instead of 13. That’s divide and conquer, the idea behind merge sort and binary search, which you’ll meet in the DSA track.

Fibonacci Using Recursion in Java (and Why It’s Slow)

The Fibonacci series goes 0, 1, 1, 2, 3, 5, 8… where fib(n) = fib(n−1) + fib(n−2). The direct recursive version recomputes the same values again and again. Memoization stores each answer the first time:

Output:

fibNaive(30) = 832040 using 2692537 callsfibMemo(30)  = 832040 using 59 calls

Same answer: 2.69 million calls versus 59. Naive Fibonacci makes an exponential number of calls (roughly doubling each time n grows by 1). With memoization each value is computed once, so the work grows linearly, O(n). This is the first step into dynamic programming.

Tower of Hanoi in Java

A classic tree recursion: move n disks from A to C using B, never putting a bigger disk on a smaller one.

Output:

Move disk 1 from A to CMove disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C
Total moves: 7 (2^3 - 1 = 7)

Types of Recursion in Java

Mutual Recursion

Output:

isEven(10) = trueisOdd(7)   = true

Does Java Optimize Tail Recursion?

No. Some languages turn a tail call into a jump, so the stack doesn’t grow. The Java language and HotSpot JVM don’t guarantee this, so even tail-recursive code overflows:

Output (JDK 25):

sumTail(1000) = 500500
sumLoop(1000000) = 500000500000
Exception in thread "main" java.lang.StackOverflowError
	at TailCall.sumTail(TailCall.java:7)
	at TailCall.sumTail(TailCall.java:7)
 ... 

Where Recursion Shines: Recursive Data

Recursion is the natural fit when the data itself is nested: folders inside folders, categories inside categories, trees and JSON. Here’s a folder tree (a record is a compact data class, Java 16+):

Output:

home (3385 KB)
  photos (3350 KB)
    2025 (1200 KB)
    2026 (1350 KB)
      goa-trip (400 KB)
  notes (30 KB) 

A loop can’t easily handle “any depth of nesting”, but recursion handles it in a few lines. The base case is implicit: a folder with no subfolders makes no further calls. (For simplicity totalKb is recalculated at every level; a real tool would compute each size once.)

Recursion vs Iteration in Java

Rule of thumb: use recursion when the problem’s shape is recursive (trees, nested data, splitting in halves). Use a loop when you’re just counting through a long sequence.

Common Mistakes With Recursion

Mistake 1: No Base Case

dive() above has no stopping condition, which leads to StackOverflowError.

Mistake 2: A Base Case That Can Be Skipped

countDownByTwo(6) prints 6 4 2 Liftoff!, but countDownByTwo(5) prints 5 3 1 -1 -3 -5 … and ends in StackOverflowError, because it jumps over 0.

Mistake 3: Using n-- Instead of n - 1

Output (with a counter added, JDK 25):

 StackOverflowError after 23254 calls - n never changed

n-- passes the current value, then decrements. Every call receives 3. Fix: countDown(n - 1).

Mistake 4: Forgetting to Return the Recursive Result

MissingReturn.java:7: error: missing return statement    }
    ^
1 error

Mistake 5: Exponential Recursion Without Memoization

Naive fib(30) makes 2.69 million calls. Memoize, or use a loop.

Mistake 6: Overflow in the Result

Output:

int  13! = 1932053504   (wrong: overflow)long 13! = 6227020800
long 21! = -4249290049419214848   (wrong: overflow)
Big  21! = 51090942171709440000

int works up to 12!, long up to 20!; beyond that, use BigInteger.

Best Practices

1. Write the base case first, and make sure every input eventually reaches it (use <=, not ==, when stepping by more than 1).
2. Pass n - 1, never n-- (or --n) in the recursive call.
3. Validate input (negative numbers, null) before recursing.
4. Memoize when the same subproblem repeats (Fibonacci-like recursion).
5. Prefer loops for deep linear recursion. Java doesn’t optimize tail calls.
6. Use recursion for recursive shapes: trees, nested data, divide and conquer, backtracking.
7. Pick a wide enough return type: long or BigInteger for factorials and powers.

Interview Questions on Recursion

How to answer in an interview: “What is recursion?”
“Recursion is when a method calls itself on a smaller version of the problem. It needs a base case that returns directly and a recursive case that moves toward it. Each call gets its own stack frame, so too many nested calls cause a StackOverflowError. Java doesn’t do tail-call optimization, so for deep linear work I’d use a loop, and for repeated subproblems I’d add memoization.”

Output-Prediction Questions

Q1.

Answer: 123. The print happens after the recursive call, on the way back.

Q2.

Answer: 105. That’s 7 × 5 × 3 × 1.

Q3. static void h(int n) { if (n == 0) return; h(n--); } called with h(2).
Answer: StackOverflowError. n-- passes 2 every time.

Conceptual Follow-Ups

1. What are the two parts of every recursive method? The base case and the recursive case.
2. Why does deep recursion cause StackOverflowError? Each active call holds a frame on a fixed-size thread stack.
3. Does Java optimize tail recursion? No, it’s not guaranteed; convert it to a loop.
4. Time complexity of naive vs memoized Fibonacci? Exponential vs O(n).
5. Can every recursive solution be written iteratively? Yes, using a loop and, if needed, an explicit stack.

More: Java Interview Questions for Freshers · Intermediate Questions · DSA track

Practice Exercises

1. Easy: Print the numbers from n down to 1 recursively, then from 1 up to n.
2. Easy: Write static int countDigits(int n) recursively (handle 0).
3. Easy–Medium: Write static boolean isPalindrome(String s) recursively.
4. Medium: Write static int gcd(int a, int b) using Euclid’s rule gcd(a, b) = gcd(b, a % b).
5. Medium: Write static long countPaths(int rows, int cols) for a grid, then add memoization and compare call counts.

Practise on ExamAdda Practice and test in the ExamAdda Compiler.

FAQs

1. What is recursion in Java?
Recursion is a technique where a method calls itself to solve a smaller version of the same problem, stopping at a base case that returns an answer directly.

2. What is a base case in recursion?
It’s the condition where the method returns without calling itself again, such as n == 0 for factorial. Without a reachable base case, the recursion never stops.

3. Why do I get StackOverflowError in recursion?
Each call uses a frame on the thread’s stack, which has a fixed size. Missing or unreachable base cases, or simply very deep recursion, fill the stack.

4. How deep can recursion go in Java?
There’s no fixed limit. It depends on stack size (-Xss) and frame size. On default JDK 25 settings, a minimal method reached about 10,000–23,000 calls in our tests.

5. Does Java support tail call optimization?
No. The JVM doesn’t guarantee it, so tail-recursive methods still grow the stack. Convert deep tail recursion into a loop.

6. Is recursion faster than loops in Java?
Usually not. Each call has overhead and uses stack memory. Recursion is chosen for clarity on recursive problems, not for speed.

7. What is memoization?
Storing the result of each subproblem the first time it’s computed, so repeated calls return it instantly. It turns naive Fibonacci’s millions of calls into dozens.

Article Summary

• Recursion means a method calls itself on a smaller input; it needs a reachable base case and a recursive case that moves toward it.
• Each call adds a stack frame; calls pile up until the base case, then unwind and combine results.
• Too-deep or endless recursion throws StackOverflowError; the depth limit varies with stack size and JIT, and Java doesn’t optimize tail calls.
• Tree recursion such as Fibonacci can be exponential; memoization brings it down to O(n).
• Use recursion for nested data and divide and conquer, and loops for long linear work.

Next → Pass by Value in Java · ← Previous: Variable Arguments (Varargs)

References: JVM Spec §2.5.2: Java Virtual Machine Stacks · Javadoc: StackOverflowError · Javadoc: BigInteger