Welcome to Programming and Data Structures

In the last chapter, we learned to implement core list algorithms iteratively (printing a list, deleting all its memory, copying a list, etc...). However, it is also possible to use recursion to do any of these jobs. In fact, recursion is often a natural fit for working with linked lists since each node points to the next node, which is itself a linked list (or null if it is the end of the list). This means that many operations on linked lists can be defined in terms of operations on smaller linked lists.

Learning to think recursively about linked lists is also good practice for learning to think about recursion in more complex pointer based structures like trees. Many algorithms on trees are defined recursively and most naturally implemented using recursion. Practicing recursion with linked lists is a good stepping stone to understanding those more complex algorithms.

The output of every recursive function on a linked list will differ. But the inputs will often be similar. Each recursive call will be responsible for processing one node. The rest of the list is “somebody else’s problem”. So, a recursive function will always take as an input a pointer to the node it is responsible for. We will call that pointer current.

The function has access to the data in the current node, and to the next pointer. But it should generally not care about what is actually being pointed to. Any node that is beyond the current node is the responsibility of the next recursive call.

The first recursive call will typically be passed the head pointer of the list. Each subsequent recursive call will be passed the next pointer of the current node, which points to the next node in the list (or nullptr if we are at the end of the list).

This diagram helps us think about how to identify a base case. The base case should be a situation where we can answer the given question, or do the operation, without having to break the problem down any further. In the case of a linked list, that will often be when the current pointer is nullptr, indicating we have reached the end of the list. So our basic logic will often look like this:

if (current == nullptr) {
    // reached end of the list
    // base case logic
    return ...;
}
// recursive case logic

Defining our base case this way means that we can gracefully handle empty lists as well. If the list is empty, the head pointer will be nullptr. The first call to our recursive function will be passed that nullptr head pointer. The base case will immediately be satisfied and we can return the appropriate result for an empty list.

We can also define our base case by looking to see if we are in the last node (i.e., if current->next is nullptr):

if (current->next == nullptr) {
    // this is the last node
    // base case logic
    return ...;
}
// recursive case logic

However, using that approach, we have to be careful to handle the empty list case separately. If the list is empty, the first call will be passed a nullptr head pointer. Trying to access current->next in that case would lead to a runtime error. So unless there is a good reason to stop at the last node, it is often better to let the recursion continue until we actually reach nullptr.