☕ Java📅 Day 19

Recursion in Java

Write methods that call themselves: base case and recursive case, factorial, Fibonacci, the call stack and StackOverflowError.

🎯

Learning objectives

→Explain recursion: a method that solves a problem by calling itself on a smaller version
→Identify the base case and the recursive case in any recursive method
→Write recursive factorial, Fibonacci and digit-based methods
→Understand the call stack and why a missing base case causes StackOverflowError

💡 Key points

A recursive method solves a problem by calling itself on a smaller version of the same problem.
Every recursive method needs a base case: a condition where it returns an answer without calling itself.
The recursive case must move towards the base case (n - 1, n / 10, a shorter string), otherwise the calls never stop.
Each call gets its own copy of the parameters and local variables, kept on the call stack until that call returns.
With no base case, or one that is never reached, calls pile up until Java throws StackOverflowError.
Any recursion can be rewritten as a loop. Recursion is often clearer for self-similar problems, while loops use less memory.
Plain recursive Fibonacci repeats the same work again and again: fib(25) makes 242,785 calls.

💻 Code examples(6)

#1Countdown: the simplest recursion

java

public class Countdown {
    static void countdown(int n) {
        if (n == 0) {                    // base case
            System.out.println("Blast off!");
            return;
        }
        System.out.println(n);
        countdown(n - 1);                // recursive case
    }

    public static void main(String[] args) {
        countdown(3);
    }
}

Output

3
2
1
Blast off!

countdown(3) prints 3 and calls countdown(2), and so on. When n reaches 0 the base case prints the message and returns without another call, so the chain stops.

#2Factorial

java

public class Factorial {
    static long fact(int n) {
        if (n <= 1) {
            return 1;                    // base case
        }
        return n * fact(n - 1);          // recursive case
    }

    public static void main(String[] args) {
        System.out.println(fact(5));
        System.out.println(fact(10));
        System.out.println(fact(20));
    }
}

Output

120
3628800
2432902008176640000

fact(5) = 5 × fact(4) = 5 × 4 × fact(3), and so on, until fact(1) returns 1. The results are then multiplied on the way back. The method returns long because 13! is already too big for an int.

#3Watching the call stack

java

public class Trace {
    static int fact(int n) {
        System.out.println("call fact(" + n + ")");
        if (n == 1) {
            return 1;
        }
        int result = n * fact(n - 1);
        System.out.println("fact(" + n + ") = " + result);
        return result;
    }

    public static void main(String[] args) {
        fact(4);
    }
}

Output

call fact(4)
call fact(3)
call fact(2)
call fact(1)
fact(2) = 2
fact(3) = 6
fact(4) = 24

The calls go down until the base case, then the answers come back up in reverse order. The call stack works like a pile of plates: the last call made is the first to finish.

#4Fibonacci and its hidden cost

java

public class Fibonacci {
    static int calls = 0;

    static int fib(int n) {
        calls++;
        if (n <= 1) {
            return n;            // fib(0)=0, fib(1)=1
        }
        return fib(n - 1) + fib(n - 2);
    }

    public static void main(String[] args) {
        for (int i = 0; i < 10; i++) {
            System.out.print(fib(i) + " ");
        }
        System.out.println();

        calls = 0;
        System.out.println("fib(25) = " + fib(25));
        System.out.println("calls: " + calls);
    }
}

Output

0 1 1 2 3 5 8 13 21 34 
fib(25) = 75025
calls: 242785

Two base cases (0 and 1) stop the recursion. But every call makes two more, so fib(25) needs 242,785 calls for just 26 different values. A simple loop would need about 25 steps.

#5Digits, powers and strings

java

public class MoreRecursion {
    static int sumDigits(int n) {
        if (n < 10) {
            return n;
        }
        return n % 10 + sumDigits(n / 10);
    }

    static long power(int base, int exp) {
        if (exp == 0) {
            return 1;
        }
        return base * power(base, exp - 1);
    }

    static String reverse(String s) {
        if (s.isEmpty()) {
            return "";
        }
        return reverse(s.substring(1)) + s.charAt(0);
    }

    public static void main(String[] args) {
        System.out.println(sumDigits(4096));
        System.out.println(power(2, 10));
        System.out.println(reverse("Delhi"));
    }
}

Output

19
1024
ihleD

Each method shrinks the problem: n / 10 drops the last digit, exp - 1 lowers the power, and substring(1) drops the first character. Each one stops at the simplest input it can answer directly.

#6No base case: StackOverflowError

java

public class NoBase {
    static int depth = 0;

    static void forever() {
        depth++;
        forever();             // no base case!
    }

    public static void main(String[] args) {
        try {
            forever();
        } catch (StackOverflowError e) {
            System.out.println("StackOverflowError!");
            System.out.println("Depth over 1000: "
                + (depth > 1000));
        }
    }
}

Output

StackOverflowError!
Depth over 1000: true

Each call takes a little stack memory and none of them ever returns, so the stack fills up. The exact depth depends on your computer, so the program only checks that it is large. Catching the error is just for this demo; the real fix is a correct base case.

🎯 Practice

Q1. What are the two parts every recursive method needs?+

A base case that returns an answer directly, and a recursive case that calls the method on a smaller input, moving towards the base case.

Q2. What does mystery(4) return? static int mystery(int n) { if (n == 0) return 0; return n + mystery(n - 1); }+

10. It works out 4 + 3 + 2 + 1 + 0, which is the sum of 1 to n.

Q3. Find the bug: static int fact(int n) { return n * fact(n - 1); }+

There is no base case. It keeps calling fact(0), fact(-1), fact(-2) and so on until StackOverflowError. Add if (n <= 1) return 1; as the first line.

Q4. Write a recursive method that counts the digits of a positive int.+

static int countDigits(int n) { if (n < 10) return 1; return 1 + countDigits(n / 10); } // countDigits(52019) gives 5

Q5. Rewrite factorial using a loop instead of recursion.+

static long fact(int n) { long result = 1; for (int i = 2; i <= n; i++) { result *= i; } return result; }

📝 Notes

How to think recursively

Find the smallest case you can answer immediately. For digits, that is a one-digit number. For a string, it is an empty string.
Trust the method to work for a smaller input, even though you are still writing it.
Build the answer for n from that smaller answer.

For sumDigits(4096): the sum of the digits of 409, plus 6. You don't need to trace the whole chain to know that it is right.

Recursion vs loops

A loop repeats inside one method call. Recursion creates a new call, with its own memory, every time.
Recursion suits problems that contain smaller copies of themselves, such as factorial, tree structures, folders inside folders, and Tower of Hanoi.
Loops suit plain counting and are safer for very large inputs, because deep recursion can overflow the stack.

// same result, no recursion
long result = 1;
for (int i = 2; i <= 5; i++) {
    result *= i;
}
System.out.println(result);   // 120

Common mistakes

A base case that can be skipped. With if (n == 1), calling fact(0) or fact(-3) never reaches it. Use n <= 1.
Ignoring the result. Writing fact(n - 1); on its own line throws the answer away. Use it: return n * fact(n - 1);
Using int for big results. 13! is 6,227,020,800, which does not fit in an int. Use long.
Recursing too deep. Something like sum(1000000) can hit StackOverflowError even with a correct base case. Use a loop for very large inputs.

Next: Day 20, ArrayList and Collections. You will use lists that grow as needed and maps that look up values by key.