Recursion · Java · CodeMIRAI

A recursive method calls itself. It solves a problem by reducing it to a smaller copy of the same problem, until the copy is small enough to answer directly.

Java

public class Main {
    static void countdown(int n) {
        if (n == 0) {                    // base case: stop here
            System.out.println("Liftoff!");
            return;
        }
        System.out.println(n);
        countdown(n - 1);                // recursive step: a smaller problem
    }

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

Every recursive method needs two parts:

a base case, which answers without recursing, and
a recursive step, which moves closer to the base case every time.

Factorial

5! means 5 × 4 × 3 × 2 × 1, and it's also 5 × 4!, a smaller factorial. That's a recursive definition:

Java

public class Main {
    static long factorial(int n) {
        if (n <= 1) return 1;
        return n * factorial(n - 1);
    }

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

How factorial(4) unfolds, and then folds back up:

Diagram

factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * (3 * (2 * 1))
= 24

More examples

Java

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

    static String reverse(String s) {
        if (s.length() <= 1) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }

    static boolean isPalindrome(String s) {
        if (s.length() <= 1) return true;
        if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
        return isPalindrome(s.substring(1, s.length() - 1));
    }

    public static void main(String[] args) {
        System.out.println(digitSum(2024));          // 8
        System.out.println(reverse("recursion"));    // noisrucer
        System.out.println(isPalindrome("racecar") + " " + isPalindrome("java"));
    }
}

Stack overflow

Each call waits on the call stack until the call it made returns. Without a base case, calls pile up until the stack runs out of room:

Java

public class Main {
    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 after " + depth + " calls");
        }
    }
}

Thousands of calls deep, Java gives up with a StackOverflowError. (Catching it is only for this demonstration; in real code, fix the missing base case.)

When recursion is slow

Java

public class Main {
    static long calls = 0;

    static long fib(int n) {
        calls++;
        if (n < 2) return n;
        return fib(n - 1) + fib(n - 2);
    }

    static long fibLoop(int n) {
        long a = 0, b = 1;
        for (int i = 0; i < n; i++) {
            long next = a + b;
            a = b;
            b = next;
        }
        return a;
    }

    public static void main(String[] args) {
        System.out.println("fib(30) = " + fib(30) + ", using " + calls + " calls");
        System.out.println("fibLoop(30) = " + fibLoop(30) + ", using 30 loop steps");
        System.out.println("fibLoop(90) = " + fibLoop(90));
    }
}

The recursive Fibonacci recalculates the same values over and over: more than 2.6 million calls for fib(30), and fib(90) would take longer than you'd want to wait. The loop takes 30 steps. Recursion shines on problems that really are recursive, like folders inside folders, trees, and divide-and-conquer sorting. For simple repetition, a loop is usually better.