CMUQ 15-121 Recursion

• 1. Introduction
• 2. The Layout of a Recursive Function
• 3. Simple Example: Factorial
• 4. Recursion in Linked Lists
  • 4.1. Quick Exercise: Code Tracing
• 5. Strategy for Designing Recursive Solutions
• Final Thoughts

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:

• Base Case (when we stop): \(0! = 1\)
• Recursive Case: \(n! = n * (n-1)!\)

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:

• Base Case: When the current node equals null, return without recursing.
• Recursive Case: Print the current node, recurse on the rest of the list.

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);
    }
}

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 + " --> ");
    }
}

5. Strategy for Designing Recursive Solutions

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

• Think of the smallest size of the problem and write down the solution (base case)
• Be optimistic. Assume you magically have a working function to solve the problem.
  • How could you use it on a smaller size input and use the answer to solve the bigger size problem? (recursive case)
• Make sure the recursive case leads to the base case.

When actually coding your recursive solution, consider these tips:

• Start with an if statement that distinguishes between the base case and recursive case.
• Solve the base case (or cases) first. You need to solve them directly without recursion. Usually these should be very simple.
• Write your recursive case to solve a small piece of the problem and then recurse to solve the rest.
• Statements written before the recursive call are evaluated on the way to the base case, while statements after the recursive call run on the way back from the base case.

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.