Home Recursion

Here is an example of a mutually-recursive set of methods. The isEven method recursively calls the isOdd method, which will also recursively call the isEven method:

public boolean isEven(int n) {
    if (n == 0) {
        return true;
    } else {
        return isOdd(n - 1);
    }
}

public int isOdd(int n) {
    if (n == 0) {
        return false;
    } else {
        return isEven(n - 1);
    }
}

While there is nothing inherently bad about mutual recursion (and indeed, it's a viable technique to use for certain kinds of problems), you should not write mutually recursive methods while taking CSE 142 and 143.

The reason for this is because most students who write mutually-recursive methods end up writing confusing code that is very difficult to reason about (and grade!). One of the core ideas underneath recursion is to build up a recursive method using its preconditions and postconditions using inductive reasoning. It gets harder to do that when you need to track preconditions and postconditions across multiple functions.

We're also careful to structure our assignments and exam problems so that you never need to use them (and so that the cleanest solution doesn't use them at all). So, if you find yourself wishing that you could use mutual recursion, it's typically a sign that there's a better way to do whatever you want to do.

Do note that writing a public-private pair, or using helper methods inside a recursive method are both completely fine, as long as your core recursive method is singly-recursive. For example, the following method is ok:

// Print information about this file, and any files inside it
// (if it's a directory)
//
// Preconditions: 
// - The file must exist in the filesystem.
//
// Postconditions:
// - Prints neatly-formatted info about the given file
public static void crawl(File file) {
    crawl(file, 0);
}

// Prints information about the file, and any of its sub-files,
// indented to the specified level.
//
// Preconditions:
// - The file must exist in the filesystem
// - The indent level must be a positive integer
//
// Postconditions:
// - Prints neatly-formatted info about the given file,
//   indented to the specified level.
private static void crawl(File f, int indentLevel) {
    String information = getInfo(file);
    System.out.println(indent(information, indentLevel));
    if (file.isDirectory()) {
        for (File subFile : file.listFiles()) {
            crawl(subFile, indent + 1);
        }
    }
}

private String getInfo(File file) {
    // ...
}

private String indent(String info, int indentLevel) {
    // ...
}

Notice that despite how this code snippit is a public-private pair, and uses several helper methods, the recursive method (the private crawl only ever recursively calls itself.