Recursion

ed Lesson

Table of contents

• Recursion
• Method calls
• Scope

Recursion

Recursion is a method for solving programming problems. In general, all programs take parameters (input), perform some computation, and return or otherwise produce a result (output). Recursive programs are different in how they perform the computation. Rather than solve the problem directly, recursive programs:

1. Take a given input and identify smaller subproblems that can be solved independently.
2. Solve each smaller subproblem using a recursive call.
3. Compute the final result by combining the results of each subproblem.

We’ll first see how recursion can solve problems that we already know how to solve. It won’t be clear how recursion helps just yet. Later, we’ll learn about many important problems that can be solved in a much more effective way using recursion rather than the alternatives.

Say we want to implement writeStars, a method that takes an integer n and prints out that number of asterisks * followed by a new line. The most natural way to solve this is to use iteration.

// pre : n >= 0
// post: Prints a line containing the given number of stars
public static void writeStars(int n) {
    for (int i = 0; i < n; i++) {
        System.out.print("*");
    }
    System.out.println();
}

In order to solve the writeStars problem using recursion, we’ll temporarily disallow ourselves from using iteration. (This is not a general rule: we’ll later see more complicated recursive problems that use both recursion and iteration to solve problems.)

One way to solve this problem without using any loops is to write out every possible case using if statements.

public static void writeStars(int n) {
    if (n == 0) {
        System.out.println();
    } else if (n == 1) {
        System.out.print("*");
        System.out.println();
    } else if (n == 2) {
        System.out.print("*");
        System.out.print("*");
        System.out.println();
    } else if (n == 3) {
        System.out.print("*");
        System.out.print("*");
        System.out.print("*");
        System.out.println();
    } ...
}

This gets tedious very quickly. How do we even cover all of the possible values of n?

This is where recursion helps. We can notice that the n == 3 case is using most of the same code from n == 2 but with an extra asterisk at the beginning. In order to run this code, we need to call writeStars(2) to execute the code in that if condition.

public static void writeStars(int n) {
    if (n == 0) {
        System.out.println();
    } else if (n == 1) {
        System.out.print("*");
        System.out.println();
    } else if (n == 2) {
        System.out.print("*");
        System.out.print("*");
        System.out.println();
    } else if (n == 3) {
        System.out.print("*");
        writeStars(2);
    } ...
}

We can also see that n == 2 contains some of the same code as the n == 1 case. Likewise, n == 1 can also substitute the println call for writeStars(0).

public static void writeStars(int n) {
    if (n == 0) {
        System.out.println();
    } else if (n == 1) {
        System.out.print("*");
        writeStars(0);
    } else if (n == 2) {
        System.out.print("*");
        writeStars(1);
    } else if (n == 3) {
        System.out.print("*");
        writeStars(2);
    } ...
}

More generally, every case except for n == 0 can be rewritten with two statements.

1. System.out.print("*");
2. writeStars(n - 1);

public static void writeStars(int n) {
    if (n == 0) {
        // Base case
        System.out.println();
    } else {
        // Recursive case
        System.out.print("*");
        writeStars(n - 1);
    }
}

This recursive program has two parts: a base case and a recursive case.

Base case

A simple input that is computed directly.

Recursive case

A more complex input that is computed with recursive calls to smaller cases.

Method calls

How does recursion work? In order to know how recursion works, we need a solid understanding of how Java evaluates method calls.

A method in Java is a defined procedure that runs the code defined in its body. For example, suppose we had the following program.

public static void main(String[] args) {
    System.out.println("main start");
    methodExample();
    System.out.println("main end");
}

public static void methodExample() {
    System.out.println("method start");
    System.out.println("method end");
}

When we run this program, we would see the following output.

main start
method start
method end
main end

When we call a method, the program “pauses” and runs the statements inside the method we called. Once that method finishes, the program resumes execution at the method call. This is why we see “method start” and “method end” in between the output for “main start” and “main end”.

When we call a method in Java, the program pauses and executes the entirety of that method before returning to running the remaining instructions after the method call. Java keeps track of where we left off so it can resume execution when the method call ends.

Here’s a trace of the steps performed by Java to run the earlier program.

Executing method:main
    println "main start"
    Pause method:main and call method:methodExample. Executing method:methodExample
        println "method start"
        println "method end"
    Finished executing method:methodExample, Resume method:main from where we left off
    println "main end"

In reality, println is also a method call, but we don’t show its internals since the details inside println are not interesting to us.

Scope

Each method has its own scope (working set of variables) that it maintains for the lifetime of its execution. Parameters are special variables in the method’s scope that are initialized with arguments from the client. Since parameters are just special variables, this means that the same rules as variables apply. For instance, changing a variable created in one scope, won’t change a different variable in a different scope.

public static void main(String[] args) {
    int x = 5;
    System.out.println("main start        : x=" + x);
    methodA(x, x + 2);
    int y = x + 4;
    System.out.println("main middle       : x=" + x + ", y=" + y);
    methodA(y, x + 2);
    System.out.println("main end          : x=" + x + ", y=" + y);
}

public static void methodA(int x, int z) {
    int y = x * z;
    System.out.println("  methodA start   : x=" + x + ", y=" + y + ", z=" + z);
    methodB(y);
    System.out.println("  methodA middle  : x=" + x + ", y=" + y + ", z=" + z);
    methodB(y);
    System.out.println("  methodA end     : x=" + x + ", y=" + y + ", z=" + z);
}

public static void methodB(int y) {
    System.out.println("    methodB start : y=" + y);
    y = 4;
    System.out.println("    methodB end   : y=" + y);
}

This method is complex enough to make it tedious to trace through, so we have provided the output below. The first key point is that the same “pausing” and “resuming” behavior is still there. The other key point is to consider that the variables in the “caller” methods do not change even if the callee method makes its own variables with the same name or reassigns its parameters. The idea here is that even though the various methods have variables (or parameters) with the same name, each method has its own set of variables that are independent of the others.

main start        : x=5
  methodA start   : x=5, y=35, z=7
    methodB start : y=35
    methodB end   : y=4
  methodA middle  : x=5, y=35, z=7
    methodB start : y=35
    methodB end   : y=4
  methodA end     : x=5, y=35, z=7
main middle       : x=5, y=9
  methodA start   : x=9, y=63, z=7
    methodB start : y=63
    methodB end   : y=4
  methodA middle  : x=9, y=63, z=7
    methodB start : y=63
    methodB end   : y=4
  methodA end     : x=9, y=63, z=7
main end          : x=5, y=9