Recursion

A recursive method calls itself with a smaller version of the problem. It needs a base case that returns without another recursive call.

Recursion fits naturally with recursive structures such as directory trees. Simple counting is often clearer with a loop, but it demonstrates the mechanics well.

Solve a smaller version

public class Main {
    static int nodesInPath(int parentsAbove) {
        if (parentsAbove == 0) {
            return 1;
        }
        return 1 + nodesInPath(parentsAbove - 1);
    }

    public static void main(String[] args) {
        int parentsAbove = 3;
        System.out.println(nodesInPath(parentsAbove));
    }
}

Output:

4

Each call counts one path node and asks the next call to count a shorter path. At zero parents above, the base case counts the current node.

If the argument never moves toward the base case, calls continue until Java throws StackOverflowError.

Use the same two-part pattern to calculate a factorial.