# Structural Recursion

## Table of contents

## Linked lists

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

`LinkedIntList`

is an implementation of the list ADT with one field,`ListNode front`

.- A recursive algorithm can be defined by identifying base cases, solving recursive subproblems, and then combining the result of each subproblem.
- 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); } }`

## 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.
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.
- Modify the return type to return a reference to a node.
- In the base case(s), modify the condition and return a reference to a node.
- 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;
}
}
```

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