Structural Recursion

Table of contents

1. Linked lists
2. x = change(x)

Linked lists

In this lesson, we’ll solve linked list problems with recursive algorithms by combining three key ideas.

1. LinkedIntList is an implementation of the list ADT with one field, ListNode front.
2. A recursive algorithm can be defined by identifying base cases, solving recursive subproblems, and then combining the result of each subproblem.
3. If the domain overly-constrains the subproblem representation, introduce a new private helper method with additional parameters.

What does the standard traversal for linked lists look like as a recursive algorithm?

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.

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

Recursive traversal for linked lists

Use a parameter to traverse the list. Each recursive call is responsible for processing a single ListNode by performing some computation (like printing) before moving to the next node.

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

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

The recursive traversal templates for linked lists is one example of a broader family of recursive templates known as structural recursion. The linked nodes data structure is recursive: each linked node is either null or a ListNode instance, so each recursive call processes a node according to its recursive definition.

In fact, all of the recursive programs we’ve studied so far are examples of structural recursion. When recursively reversing a string, each subproblem reduced the length of the string by 1. When recursively binary searching, each subproblem cut in half the high - low portion the sorted array. Later, we’ll study generative recursion, a family of recursive templates that doesn’t follow this pattern.

x = change(x)

Say we want to implement a recursive LinkedIntList.add method. An iterative algorithm loops through the list to the last element in order to reassign its next field to a new ListNode.

// 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 directly translate the iterative algorithm to a recursive algorithm by introducing a private helper method.

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

This code works, but the public and private methods share some redundant code. Both methods include base cases for creating the same new ListNode(value) and only differ in assigning to either the front of the list or the current.next. The x = change(x) pattern is a strategy for factoring-out this redundancy by making one additional recursive call beyond the typical base case.

x = change(x)

A recursive algorithm pattern for factoring out redundant base cases involving assignment of the same value to different fields.

1. Modify the return type to return a reference to a node.
2. In the base case(s), modify the condition and return a reference to a node.
3. In the recursive case(s), assign the returned node reference to a field.

Note that the condition for the base case now checks that current == null rather than current.next == null. Instead of stopping at the last node, the recursive calls continue until current == null.

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

The x = change(x) concept is something that we might remember from our earlier definition of functional abstraction: we’re using the return values to help compute the complete result. Formally, we define the range as the possible return values of a function.

In recursive algorithm design, there are two ways of communicating between the current recursive problem and its subproblems.

Domain

The current recursive problem can send information to its subproblems by passing them as inputs (parameters).

Range

The current recursive problem can receive information from its subproblems by processing their outputs (return values).