CMUQ 15-121 Recursion



1. Introduction

A recursive method is a method that calls itself. You’ve been exposed to recursion before, so consider these notes a brief refresher on the topic.

For an example, please see Section 1, Introduction.

2. The Layout of a Recursive Function

Every recursive function includes two parts:

  1. The non-recursive base case. This is one or more simple cases that can be solved immediately.
  2. The recursive case. This is one or more cases that solve a small piece of the overall problem and then recurse to solve the rest.

3. Simple Example: Factorial

Consider the following recursive way to solve for the factorial of \(n\), \(n!\).

The nice thing about factorial is that the problem itself is naturally recursive, because:
\(n! = n * (n-1)!\)

Of course, the problem isn’t recursive all the way down. The special case is \(0!\), because that one can’t be written recursively. Instead, we just know that \(0! = 1\).

Given this, we can define factorial recursively as:

A recursive, Java solution would therefore look like:

public static int factorial(int n) {
    // Base Case
    if (n == 0) {
        return 1;
    }
    // Recursive Case
    else {
        return n * factorial(n-1);
    }
}

Take some time to study that code, run it, add prints to it, etc. Make sure you understand how and why it works.

4. Recursion in Linked Lists

Many linked list methods can be written recursively. (Although most probably shouldn’t, there are times when recursion will make something much easier.)

Consider trying to write a recursive printList(ListNode head) method. You can think of it recursively as: Print the head of the list, then recurse on the rest of the list. Of course, this could go on forever, so how do we know when to stop? We stop when head == null, meaning there is no more list.

Given this, we can define printing a linked list recursively as:

Here is some Java code for it:

public static void printNodes(ListNode head) {
    // Base case
    if (head == null) {
        System.out.println("<null>");
        return;
    }
    // Recursive case
    else {
        System.out.print(head.data + " --> ");
        printNodes(head.next);
    }
}

4.1. Quick Exercise: Code Tracing

Here is another version of printNodes that is only different in that lines 9 and 10 have had their order switched.

public static void printNodes(ListNode head) {
    // Base case
    if (head == null) {
        System.out.println("<null>");
        return;
    }
    // Recursive case
    else {
        printNodes(head.next);
        System.out.print(head.data + " --> ");
    }
}

What does this change about the output? Why?

5. Strategy for Designing Recursive Solutions

When designing your recursive solution, try to think of the problem in this way:

When actually coding your recursive solution, consider these tips:

Final Thoughts

Recursion and iteration (using loops and such) are both equally expressive, which means that either one can be used to solve any problem. However, some problems are easier to solve with recursion while others are easier to solve with iteration. Usually, a iterative approach will be best. As we continue learning more data structures, however, we’ll find that certain data structures are inherently easier to work with recursively.