# Structural Recursion

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?

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

The implicit base case occurs when `current == null`. There is nothing left to do in the traversal.

In the recursive case, the method prints out the `current.data` and makes a recursive call to process the next element in the list.

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

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

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

private ListNode add(ListNode current, int value) {
if (current == null) {
return new ListNode(value);
} else {
return current;
}
}
``````
Why return current in the recursive case?

The practical reason is to satisfy the Java compiler: the code won’t run unless every if-case returns a `ListNode`. By returning `current` back to the caller, the current recursive subproblem is signaling that no change is necessary to the current linked node structure. Remember that each recursive case will reassign `current.next`, but in a long linked list, many of these `next` fields don’t need to be changed.

Why reassign front in the public method?

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`. That new `ListNode` is the new `front` of the list!

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).