Structural recursion

ed Lesson

Table of contents

• Linked lists
• x = change(x)

Linked lists

In this lesson, we’ll apply recursion to solve linked list problems by synthesizing ideas from four earlier lessons.

1. ListNode is a recursive data structure with two fields, int data and ListNode next.
2. LinkedIntList is an implementation of the list abstract data type with a single field, ListNode front.
3. Iteration can be converted to recursion by identifying variables that need to be shared between recursive calls and treating them as parameters.
4. It’s sometimes necessary to introduce a new private method with additional parameters for handling additional data passed from one recursive call to the next.

What does the standard traversal for linked lists look like using recursion?

Iterative traversal for linked lists

Use a local variable to traverse the list. At each ListNode, perform some computation (like printing) before moving to the next node.

Implementer

public void print() {
    ListNode current = front;
    while (current != null) {
        System.out.print(current.data + " ");
        current = current.next;
    }
}

Recursive traversal for linked lists

Instead of using a local variable, use a parameter to traverse the list. This often requires introducing a public/private pair. At each recursive call, perform some computation (like printing) before moving to the next node.

Implementer

public void print() {
    print(front);
}

private void print(ListNode current) {
    if (current != null) {
        System.out.print(current.data + " ");
        print(current.next);
    }
}

x = change(x)

Earlier, we saw how information can be shared from recursive calls to their subproblems by passing them as parameters. This data is shared as inputs to new recursive calls. How do we go the other way and communicate information from a subproblem back to the main problem?

If we want to communicate information to the caller of a method, we need to utilize the return value!

public static void main(String[] args) {
    Point p = new Point(1, 2);
    p = change(p);
}

public static Point change(Point p) {
    return new Point(7, 8);
}

This pattern is not particularly useful for Point instances since they’re not recursive. We could have redefined change to take in no arguments since the Point p parameter is never used.

However, this x = change(x) pattern is very useful for simplifying recursive linked list code. Say we want to reimplement the LinkedIntList.add method using recursion rather than iteration. The iterative solution loops through the list until the pointer is at the last element before reassigning its next field to a new ListNode.

Implementer

// post: Appends the given value to the end of the list.
public void add(int value) {
    if (front == null) {
        front = new ListNode(value);
    } else {
        ListNode current = front;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new ListNode(value);
    }
}

We can literally translate the iterative implementation to recursion by introducing a private helper method to pass the reference to the next ListNode current.

Implementer

public void add(int value) {
    if (front == null) {
        front = new ListNode(value);
    } else {
        add(front, value);
    }
}

private void add(ListNode current, int value) {
    if (current.next == null) {
        current.next = new ListNode(value);
    } else {
        add(current.next, value);
    }
}

However, there is redundant code in the base cases: both the public and private methods create a new ListNode instance. This is the perfect place to use the x = change(x) pattern. Note that we changed the return type of the private helper method to return a reference to the new ListNode where it’s needed in both the public and private methods.

Implementer

public void add(int value) {
    front = add(front, value);
}

private ListNode add(ListNode current, int value) {
    if (current == null) {
        return new ListNode(value);
    } else {
        current.next = add(current.next, value);
        return current;
    }
}

Let’s consider what happens when we take call [1, 2].add(3).

1. Call the public add(3) method of the list, which calls the private helper method with a reference to [1] -> ....
   1. Since current != null, use the recursive case and call the helper method with a reference to [2] /.
      1. Since current != null, use the recursive case and call the helper method with a reference to null.
         1. Since current == null, use the base case and return a reference to a new ListNode with value 3: [3] /
      2. Assign the reference to the new ListNode to the next field: [2] -> [3] /.
      3. Return the reference to the ListNode current: [2] -> ....
   2. Assign the reference to [2] -> ... to the next field. (This assignment statement does not change the picture!)
   3. Return the reference to the ListNode current: [1] -> ....
2. Assign the reference to [1] -> ... to the front field. (This assignment statement does not change the picture!)