DSA in Java: Recursion & Backtracking Basics (Beginner Guide)

Recursion is one of those ideas that feels like magic until it suddenly clicks — and then you can't unsee it. It's a function that calls itself to solve a problem by breaking it into smaller versions of the same problem. Recursion powers trees, graphs, sorting, and the whole family of "backtracking" problems you'll meet later. Let's demystify it with plenty of small, clear examples.

The core idea: a problem inside a smaller problem

Recursion works when a big problem contains a smaller copy of itself. Think of counting down from 5: "print 5, then count down from 4." Counting down from 4 is the same task, just smaller. Every recursive solution has exactly two parts:

• Base case — the smallest problem, which you can answer directly without recursing. This stops the recursion.
• Recursive case — you solve a smaller version of the problem and build on it.

Example 1: Factorial

The factorial of n (written n!) is n × (n-1) × ... × 1. Notice that n! = n × (n-1)! — the definition literally contains a smaller factorial. That's your recursive case; the base case is 0! = 1:

int factorial(int n) {
    if (n == 0) return 1;        // base case — stop here
    return n * factorial(n - 1);   // recursive case — smaller problem
}

How it actually runs

Let's trace factorial(3). Each call waits for the smaller call to finish, then multiplies:

factorial(3)
= 3 * factorial(2)
= 3 * (2 * factorial(1))
= 3 * (2 * (1 * factorial(0)))
= 3 * (2 * (1 * 1))      // base case reached, now unwind
= 3 * (2 * 1)
= 3 * 2
= 6

The calls stack up going down (each waiting), then resolve going back up. That "stack" is literally the call stack from the JVM lesson — each recursive call adds a frame, and reaching the base case lets them all unwind.

Example 2: Fibonacci

Each Fibonacci number is the sum of the previous two: fib(n) = fib(n-1) + fib(n-2), with base cases fib(0)=0 and fib(1)=1. It maps almost word-for-word to code:

int fib(int n) {
    if (n <= 1) return n;              // base cases: fib(0)=0, fib(1)=1
    return fib(n - 1) + fib(n - 2);      // two recursive calls
}

How to think about writing recursion

Beginners often try to trace every single call in their head and get lost. Don't. Instead, trust the recursion with three questions:

1. What's the base case? The simplest input you can answer immediately.
2. How do I make the problem smaller? Reduce toward the base case (n-1, half the array, one less item).
3. Assuming the smaller call works, how do I use its answer? Combine it to solve the current step.

This "leap of faith" — assume the recursive call already does its job correctly — is the mental shift that makes recursion easy.

A first taste of backtracking

Backtracking is recursion that tries a choice, explores further, and undoes the choice if it doesn't work out — like exploring a maze: go down a path, hit a dead end, back up, try another. It powers problems like generating all permutations, solving Sudoku, and the N-Queens puzzle. The skeleton looks like this:

void backtrack(state) {
    if (isComplete(state)) { record(state); return; }
    for (choice : choices) {
        make(choice);        // try it
        backtrack(state);    // explore deeper
        undo(choice);        // backtrack: undo and try the next
    }
}

Don't worry about mastering backtracking today — just recognise the shape. We'll return to it once you've seen more data structures.

Recursion genuinely broke my brain at first — I kept trying to trace all the calls at once and drowning. The thing that saved me was the "leap of faith": stop tracing, and just trust that the recursive call returns the right answer for the smaller problem. Once I started thinking only about the base case and one step, recursion turned from terrifying into one of my favourite tools. It'll feel weird for a week, then suddenly natural. Write these examples out by hand, trace factorial(3) on paper, and it'll click.

Key takeaways

• Recursion = a function that calls itself on a smaller version of the problem.
• Every recursion needs a base case (to stop) and a recursive case that moves toward it — miss it and you get a StackOverflowError.
• Think in three questions: base case, how to shrink, how to combine — and take the "leap of faith."
• Backtracking is recursion that tries a choice, explores, and undoes it — the basis for permutations, Sudoku, and more.

← Previous: DSA Lesson 3 — Strings & Common Patterns
Next: DSA Lesson 5 — Searching (Linear & Binary) →
↑ Back to the DSA roadmap