Java Recursion

Recursion means a method calls itself. It is a good way to solve a big problem by solving smaller copies of the same problem.

Two parts of every recursion

1. Base case: the simple case where the method stops and returns an answer.
2. Recursive case: the method calls itself with a smaller problem.

Factorial

5! = 5 x 4 x 3 x 2 x 1. The factorial of n is n times the factorial of n - 1, and 0! = 1.

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

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

See the calls

public class Trace {
    static int sum(int n) {
        System.out.println("sum(" + n + ") called");
        if (n == 0) return 0;
        int result = n + sum(n - 1);
        System.out.println("sum(" + n + ") returns " + result);
        return result;
    }

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

Fibonacci

public class Fib {
    static int fib(int n) {
        if (n <= 1) return n;
        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();
    }
}

This version is simple, but it repeats the same work again and again, so it gets very slow for big numbers (like fib(45)). A loop, or saving the results in a map (memoization), is much faster.

Sum of digits

public class Digits {
    static int digitSum(int n) {
        if (n == 0) return 0;
        return n % 10 + digitSum(n / 10);
    }

    public static void main(String[] args) {
        System.out.println(digitSum(9475));
    }
}

StackOverflowError

Every call is saved in memory on the call stack. If there is no base case (or it is never reached), the stack becomes full and Java throws a StackOverflowError:

public class Overflow {
    static int bad(int n) {
        return bad(n + 1);               // no base case
    }

    public static void main(String[] args) {
        try {
            bad(1);
        } catch (StackOverflowError e) {
            System.out.println("Caught: StackOverflowError");
        }
    }
}

Recursion or loop?

• A loop is faster and uses less memory.
• Recursion is clearer for problems like trees, folders, and divide and conquer.
• Java does not optimize deep recursion, so avoid it for thousands of levels.

• Previous Page
• Next Page

---

Exercises & Assignments
No Content Found.

Interview Questions & Answers
No Content Found.