skip to content

What is recursion in Java, and why must a recursive method have a base case?

level: juniorimportance: must knowfreq 80%

answer

  1. Method calls itself on a smaller subproblem
  2. Base case = stop condition, no recursion
  3. Recursive case must shrink toward the base case
  4. No base case -> infinite recursion -> StackOverflowError
  5. Winds down to base, unwinds back up

basics

~20 s

Recursion is when a method calls itself to solve a smaller piece of a problem. The base case is the simple input that stops the calling, so the method does not call itself forever and eventually returns an answer.

solid answer

~40 s

Recursion is a technique where a method solves a problem by calling itself on a smaller or simpler version of the same problem. Every correct recursive method needs two parts: a base case, a condition simple enough to answer directly without recursing, and a recursive case that reduces the input and calls the method again, moving toward the base case. Without a base case (or if the recursive case never approaches it) the calls never stop and the program eventually exhausts the call stack and throws StackOverflowError. A classic example is factorial: factorial(0) returns 1 (base case), and factorial(n) returns n * factorial(n-1) (recursive case). Recursion is a natural fit for self-similar problems like tree traversal, where each subtree is handled by the same logic.

code

java · 8 lines
java
static long factorial(int n) {
    if (n == 0) {        // base case: stop recursing
        return 1;
    }
    return n * factorial(n - 1); // recursive case: shrink toward base
}

// factorial(3) -> 3 * factorial(2) -> ... -> 3*2*1*1 == 6

go deeper

for a junior

Defines recursion as a method calling itself, identifies the base case as the stop condition, and can trace a simple example like factorial.

for a middle

Explains both base and recursive cases, notes the recursive case must converge toward the base case, and connects a missing base case to StackOverflowError.

for a senior

Frames recursion in terms of the call stack and stack frames, knows when recursion is the right tool (self-similar data, divide-and-conquer) versus a loop, and reasons about correctness/termination.

for a principal

Discusses recursion as a design choice with cost trade-offs (stack depth, readability), guides teams on when to convert to iteration or accumulate state, and reasons about termination proofs and input bounds.

## What recursion is **Recursion** is a problem-solving technique where a function (in Java, a *method*) is defined in terms of itself: to solve a problem, the method calls *itself* on a smaller or simpler version of that same problem, until the problem becomes trivial enough to answer directly. A **method** is a named block of code you can call. When code 'calls a method', execution jumps into that method, runs it, and then returns to where it was called. A *recursive* method is simply one whose body contains a call to itself. ## Why a base case is mandatory Every correct recursive method must have two parts: 1. **Base case** — a condition that is simple enough to answer *without* recursing. It is where the recursion stops. For `factorial`, the base case is `n == 0`, which returns `1` directly. 2. **Recursive case** — the part that does call the method again, but on a *reduced* input that moves **toward** the base case. For `factorial`, that is `return n * factorial(n - 1)` — each call passes a smaller `n`. If there is **no base case**, or the recursive case never actually approaches the base case (e.g. you pass the same value, or move away from it), the method keeps calling itself indefinitely. This is called **infinite recursion**. ## What the call stack is, and why infinite recursion crashes When any method is called, the JVM allocates a **stack frame** for it — a small block of memory holding that call's local variables, parameters, and the place to return to. These frames are stored on the thread's **call stack**, which has a fixed, limited size. Each *active* recursive call adds another frame; a frame is only freed (popped) when its call **returns**. With infinite recursion, calls keep being made but none ever returns, so frames pile up without limit. When the stack runs out of room, the JVM throws **`java.lang.StackOverflowError`**. This is the runtime symptom of a missing or unreachable base case. ## Worked example ``` factorial(3) = 3 * factorial(2) = 3 * (2 * factorial(1)) = 3 * (2 * (1 * factorial(0))) // factorial(0) hits the base case -> 1 = 3 * (2 * (1 * 1)) = 6 ``` The calls 'wind' down to the base case, then the results 'unwind' back up as each call returns and multiplies. ## Key takeaways - Recursion = a method calling itself on a smaller subproblem. - You **always** need a base case (the stop condition) and a recursive case that shrinks toward it. - The base case must actually be reachable for every valid input. - Recursion shines on **self-similar** structures (trees, nested data) and divide-and-conquer algorithms. - A missing/unreachable base case produces infinite recursion and a `StackOverflowError` at runtime.

  • What happens at runtime if the base case is never reached?
    The recursive calls never return, stack frames accumulate until the call stack is exhausted, and the JVM throws StackOverflowError.
  • Can any recursion be rewritten as a loop?
    Yes. Any recursive algorithm has an equivalent iterative form, sometimes by using an explicit stack data structure to replace the call stack.

saying these in an interview costs you the question

  • Claiming recursion can run forever safely without crashing
  • Forgetting that the recursive case must move toward the base case (having a base case alone is not enough)
  • Confusing the base case with the recursive case
  • Saying recursion is always better/cleaner than a loop

context

resolving links…