Back to Recursion
Q1Question 1 of 1

What is a recursive program?

Key Concepts
  • Recursion: a method that calls itself, breaking a problem into smaller subproblems
  • Base case: the condition that stops the recursion – without it, infinite recursion crashes the stack
  • Each recursive call pushes a new stack frame – deep recursion causes StackOverflowError
  • Default stack size: ~512KB to 1MB per thread, tunable with -Xss
  • Tail recursion: the recursive call is the last operation – Java does NOT optimize tail calls
  • For deep recursion, convert to iteration (loop) which reuses one stack frame

Definition

Recursion is when a method calls itself to solve a smaller subproblem. It needs a base case to stop. Deep recursion causes StackOverflowError because each call uses stack space.

Recursion has two parts:

  • Recursive case: The method calls itself with a smaller input. factorial(n) = n * factorial(n-1).
  • Base case: The condition that stops the recursion. factorial(0) = 1. Without a base case, the recursion is infinite and the stack overflows.

A bank manager asks the assistant to count the money in a pile. The assistant takes one note off the top, counts it, and asks another assistant to count the rest. This continues until the pile is empty (base case). If the pile is infinitely tall, the bank runs out of assistants (stack overflow).

Understanding the Concepts

How does recursion work?

JAVA
public class InterestCalculator {
    // Recursive: compound interest for n years
    public static BigDecimal compound(BigDecimal principal, BigDecimal rate, int years) {
        if (years == 0) return principal;  // base case
        BigDecimal newPrincipal = principal.add(principal.multiply(rate));
        return compound(newPrincipal, rate, years - 1);  // recursive case
    }

    public static void main(String[] args) {
        BigDecimal result = compound(
            new BigDecimal("500000"),
            new BigDecimal("0.085"),
            5
        );
        System.out.println("After 5 years: " + result);
    }
}

When does StackOverflowError happen?

JAVA
// Infinite recursion: no base case
public static int broken(int n) {
    return broken(n - 1);  // never stops → StackOverflowError
}

// Deep recursion: base case exists but n is too large
public static int countdown(int n) {
    if (n <= 0) return 0;
    return countdown(n - 1);  // works for n=10000, fails for n=1000000
}

// countdown(1_000_000) → StackOverflowError (stack exhausted)

Each call pushes a frame (~50-100 bytes) onto the stack. Default stack is ~512KB, so ~5000-10000 frames before overflow.

How do you convert recursion to iteration?

JAVA
// Recursive
public static BigDecimal compoundRecursive(BigDecimal p, BigDecimal rate, int years) {
    if (years == 0) return p;
    return compoundRecursive(p.add(p.multiply(rate)), rate, years - 1);
}

// Iterative: same result, no stack risk
public static BigDecimal compoundIterative(BigDecimal p, BigDecimal rate, int years) {
    for (int i = 0; i < years; i++) {
        p = p.add(p.multiply(rate));
    }
    return p;
}

The iterative version reuses one stack frame. It cannot overflow regardless of the number of years.

Does Java optimize tail recursion?

No. Unlike Scala or Kotlin, Java does not perform tail-call optimization. Even if the recursive call is the last statement, each call still pushes a new frame.

JAVA
// Tail-recursive: the recursive call is the last operation
// But Java does NOT optimize this – still uses stack
public static BigDecimal tailCompound(BigDecimal p, BigDecimal rate, int years) {
    if (years == 0) return p;  // base case
    return tailCompound(p.add(p.multiply(rate)), rate, years - 1);  // tail position
}
// In Scala, @tailrec would convert this to a loop. Java does not.

For deep recursion in Java, always convert to a loop.

What are common mistakes?

DIAGRAM
- **Missing base case.** Infinite recursion → StackOverflowError.
- **Base case that is never reached.** `if (n == 0)` but n starts negative → infinite recursion.
- **Using recursion for large inputs.** Use iteration for anything that could recurse more than a few thousand times.

What should a senior engineer know?

  • Increase stack size with -Xss4m if you must use deep recursion (rare).
  • Memoization (caching results) turns exponential recursion into O(n). Used in dynamic programming.
  • Trampoline pattern simulates tail-call optimization by returning a thunk instead of recursing directly.

Visual Overview

DIAGRAM
  compound(500000, 0.085, 5)
    │ years=5, not 0
    ▼
  compound(542500, 0.085, 4)
    │ years=4
    ▼
  compound(588612.50, 0.085, 3)
    │ years=3
    ▼
  compound(638644.56, 0.085, 2)
    │ years=2
    ▼
  compound(692929.35, 0.085, 1)
    │ years=1
    ▼
  compound(751828.34, 0.085, 0)
    │ years=0 → BASE CASE → return 751828.34
    ▼
  Unwind all frames → result: 751828.34

  Each call = one stack frame
  Too many calls = StackOverflowError
  Fix: convert to iteration (loop)

Key Takeaway

Recursion is when a method calls itself to solve a smaller subproblem. It needs a base case to stop, and each recursive call pushes a new stack frame. Deep recursion exhausts the stack and throws StackOverflowError.

Java does not optimize tail recursion, so even tail-recursive methods use stack space. For any problem that could recurse deeply (more than a few thousand calls), convert to iteration, which reuses one stack frame and cannot overflow.

One sentence to remember: recursion breaks a problem into smaller subproblems, needs a base case to stop, and deep recursion causes StackOverflowError – convert to a loop for large inputs.

---

Share