## Recursion on Linked Lists

Mar 122018A linked list is a recursive structure — a linked list node has a value, and a pointer to the next linked list node. This means we can solve problems on linked lists using structural recursion. In this post we’ll see three examples, to demonstrate the process of writing a structurally recursive algorithm.

The key is to focus on the *what* and *why,* not the *how*.
Before writing a structurally recursive function, we should ask ourselves two questions:

- What is the recursive structure — what “parts” resemble the “whole”?
- Why would we want to solve the same problem on the “parts”?

#### What?

A linked list node has a pointer to the next linked list node.
So if a recursive function takes a `node`

as input, the recursive call will be on `node.next`

.

```
class LinkedListNode:
def __init__(self, value, next=None):
self.value = value
self.next = next
first_node = LinkedListNode(3,
LinkedListNode(1,
LinkedListNode(4,
LinkedListNode(9)
)
)
)
```

But a single node isn’t the “whole” list, and the next node isn’t “part” of the previous node.
This is the same issue we noticed with trees: the root node is not the “whole” tree, and a child is not “part” of its parent — but each node, with its descendants, forms a *subtree* which is a “part” of the whole tree.

Thinking the same way about linked lists, if `node`

defines a “whole” list, then `node.next`

defines a *sublist* which is “part” of it; this sublist contains everything except the first value, and is normally called the “tail” of the list.

Notice that the tail — the “part” — resembles the “whole”.
However, sometimes `node.next`

will be a null pointer, meaning there is no tail; or rather, the tail is an empty list.

An empty list *doesn’t* resemble the “whole”, since it has no first value — so we will need to handle this case separately.
The correct result for an empty list will depend on what the problem is.

#### Why?

Our functions will make recursive calls on the list’s tail. The reason we should want to do this will depend on the problem — in each example, we’ll start by saying why it’s useful to solve the same problem for the list’s tail.

#### Sum of numbers in a linked list

*Problem:* Calculate the sum of the numbers in a linked list.

*Question:* Why should we calculate the sum of the numbers in the tail?

*Answer:* The sum of the whole list is the first value plus the sum of the tail.

In our example linked list, the first value is 3 and the tail’s sum is 14, so the sum of the whole list is 3 + 14 = 17.

If the list is empty, then the correct sum is 0.

```
def linked_list_sum(node):
if node is None:
return 0
else:
return node.value + linked_list_sum(node.next)
```

#### Length of a linked list

*Problem:* Calculate the length of a linked list.

*Question:* Why should we calculate the length of the tail?

*Answer:* The length of the whole list is the length of the tail, plus one.

In our example, the length of the tail is 3, so the length of the whole list is 3 + 1 = 4.

If the list is empty, then the length is 0.

```
def linked_list_length(node):
if node is None:
return 0
else:
return linked_list_length(node.next) + 1
```

#### Maximum value in a linked list

*Problem:* Find the maximum value in a linked list.

*Question:* Why should we find the maximum value in the tail?

*Answer:* The maximum of the whole list is either the first value, or the tail’s maximum, whichever is larger.

In our example, the first value is 3 and the tail’s maximum is 9, so the maximum of the whole list is 9.

If the list is empty then there *is* no maximum value, so an empty list is an invalid input.
If the *tail* is empty, on the other hand, then the list has only one value, so this is the maximum.

```
def linked_list_max(node):
if node is None:
raise ValueError('The list is empty')
elif node.next is None:
return node.value
else:
tail_max = linked_list_max(node.next)
return max(node.value, tail_max)
```

#### Recursion vs. loops

Structural recursion can be easy — to write recursive functions we need to think about *what* the structure is and *why* we should make a recursive call.
Throughout this post we never thought about *how* our functions would actually be computed; we just assumed the recursive call would give the correct result for the tail, and then did the right thing with that result.

On the other hand, we could have written all of these functions using loops instead. This function finds the sum of a linked list, without recursion:

```
def linked_list_sum(node):
t = 0
while node is not None:
t += node.value
node = node.next
return t
```

This code uses a loop, and isn’t really simpler than the recursive code, but to write it we need to think about *how* the loop works.

## There are no published comments.