# Structural recursion

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?

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;
}
}
``````
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);
}
}
``````
Identify the base case and recursive case.

The base case is when `current == null`. There is nothing left to do in the traversal. In the recursive case, `traverse` prints the `current.data` and traverses the next element in the list.

## 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.
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 {
}
}

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

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

private ListNode add(ListNode current, int value) {
if (current == null) {
return new ListNode(value);
} else {
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!)
Why is it necessary to reassign to front at the end?

Consider the case of an empty list. Since `front == null`, Java will immediately use the base case and return a reference to a new `ListNode` with the given `value`. If we do not assign that reference to `front`, the list won’t change!