DS&A

Recursion on Linked Lists

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

Footnotes

• Tags: 
• recursion, structural recursion, linked lists, algorithms