Basic Recursion and the Call Stack

A non-empty linked list splits into a head node and a tail, and the tail is itself a shorter linked list.

Programming

Summing a List Without a Loop

A linked list is usually processed with a loop. You start at the first node, move through each next reference, and stop when you reach null. Recursion is rarely the most natural tool for this job. It is still worth learning, because the same reasoning carries over to recursive processing of more complex data structures, such as trees, where a loop is less convenient.

The question this article answers is how a recursive method can work through a list one node at a time without a loop. The answer depends on seeing that a list contains a smaller list inside it. Once that is clear, the method can be written as a small number of decisions that are repeated on smaller and smaller pieces. Keep that idea in mind as you read: the whole problem gets handed down, one node smaller each time.

Splitting a List into Head and Tail

Every non-empty linked list can be split into two parts: a head node, which is the first node, and a tail, which is everything that comes after it. The tail is not some different kind of object. It is itself a linked list, and it is shorter than the original by exactly one node. This is the key fact that makes recursion a good fit: the problem about the whole list can be divided into a small piece you can handle directly, which is the head, and a smaller version of the same problem, which is the tail.

How are the head node and the tail related through the links, and why does the tail still have the same structure as the whole list?

You do not need a separate operation to obtain the tail. If the variable head refers to the first node, then head.next refers to the second node, and that second node is the first node of the tail. So head.next works as a reference to the tail. Following one reference gives you everything that remains.

Consider the list that has only one node. Its tail contains nothing, so head.next is null. An empty list is represented by a null reference, which means head.next still represents the tail even in this special case. The same expression works for every non-empty list, including the shortest one. This consistency is what lets one method handle every size without a special branch for the single-node case.

Base Case and Recursive Case in a Sum

A recursive method for adding up the integers in a linked list has two paths. The first path is the base case, which checks whether the list is empty. If it is, the sum is zero, because there are no numbers to add. The base case returns a neutral value so that the calls waiting above it have something to add to.

The second path is the recursive case, which runs when the list is not empty. It takes the number in the head node, finds the sum of the tail by calling the same method on head.next, adds the two, and returns the result. The recursive case handles only one item directly and leaves the rest to a fresh call of the same method on a smaller list.

Definition

Base case: the situation where the method returns directly without making another recursive call. For a sum over a linked list, this is the empty list, which returns 0.

Definition

Recursive case: the situation where the method handles one piece of the problem, calls itself on the smaller remainder, and combines the two results. For a sum over a linked list, the head item is added to the sum of the tail.

Tracing the Descent Through a Short List

The easiest way to see how this works is to follow one short list through every call. Take a list of three nodes holding the values 4, 7, and 2. The first call receives the whole list. Because the list is not empty, it does not add anything yet. It hands the smaller list 7 then 2 to a second call, and that call hands the list 2 to a third call. The third call hands the empty list to a fourth call. The fourth call finds the list empty and returns 0 immediately.

What is on the stack at each step as the recursive calls go deeper, and in what order do the frames get removed as values return?

Read the stack from the top. The first call is the outermost one, and it is the last to finish. The empty list at the bottom is the deepest call, and it is the first to finish. Each call above it is paused, waiting for a single value to come back, which is the tail sum it asked for. The descent is the first half of the computation. No addition has happened yet.

Unwinding and Building the Total

Once the base case returns 0, the waiting calls resume one at a time, starting with the deepest. Each resumed call adds its own head item to the tail sum it just received and returns that total to the call that is waiting for it. This process is called unwinding. It is the second half of every recursive computation, and it is where the actual addition happens.

In what order are the calls made and the sums returned, and at which step could a returned value be dropped or added incorrectly?

Worked example

Unwinding the sum of 4, 7, and 2

Find the value returned by the first call when the list holds 4, 7, and 2.

1
Base case
Call 4 receives the empty list and returns 0.
2
Call 3 resumes
Its head is 2. It adds 2 to the returned 0 and returns 2.
3
Call 2 resumes
Its head is 7. It adds 7 to the returned 2 and returns 9.
4
Call 1 resumes
Its head is 4. It adds 4 to the returned 9 and returns 13.

Result

The first call returns 13, which is the sum of all three values.

Unwinding explains why the recursive case must use the value returned by the call. Each call is waiting for exactly one number, and that number carries the contribution of the rest of the list back up to the top. The head item is always added to that returned value, never used alone.

Writing the Recursive Sum

The method has the same two parts as the algorithm. The first check handles the base case. The final line handles the recursive case: it reads the head value, makes a recursive call on head.next, and combines the two into the return value. The code below is a generated example that follows this plan, with a small Node class so the list can be built and tested.

Code walkthrough

class Node:
    def __init__(self, value, next_node=None):
        self.value = value
        self.next = next_node

def sum_list(head):
    if head is None:
        return 0
    return head.value + sum_list(head.next)

a = Node(4, Node(7, Node(2)))
print(sum_list(a))

1
Lines 1 to 3 define Node, which holds a value and a next reference. A node with next_node set to None is the last node.
2
Line 6 defines sum_list, which receives the head of a list. The head is the first node or None for an empty list.
3
Lines 7 and 8 handle the base case: when head is None, the list is empty and the method returns 0 without calling itself.
4
Line 9 handles the recursive case in one expression. It takes head.value, calls sum_list on head.next, adds the two, and returns the total.
5
Lines 11 and 12 build the list 4, 7, 2 and print the result, which is 13.

The Node class stores a value and a reference named next.
The if head is None check is the base case for the empty list.
The return line is the recursive case: head.value is the head item, and sum_list(head.next) is the call on the tail.

Output

What do you think happens?

What does sum_list return for a list that contains only one node holding the value 9?

Reveal answer

Answer:

The head is not None, so the recursive case runs. It returns 9 plus sum_list(None), and sum_list(None) returns 0. So the total is 9.

Where a Returned Value Can Go Wrong

Recursive sums are easy to get wrong in ways that still look plausible. The most important place to check is the unwinding step, because that is where each call's head item must be combined with the value it received. The mistakes below are common in this kind of method.

Common mistake
Ignoring the value returned by the recursive call
What it looks like
return head.value
Why it fails
The tail sum is computed nowhere in the result, so only the first item survives. Unwinding has nothing to add to.
Do this instead
```
return head.value + sum_list(head.next)
```
Common mistake
Returning the wrong neutral value for the base case
What it looks like
```
if head is None: return None
```
Why it fails
The base case must return the neutral value for a sum, which is 0. Returning None makes the addition in the calls above it fail.
Do this instead
```
if head is None: return 0
```
Common mistake
Making the recursive call on the same list instead of the tail
What it looks like
```
return head.value + sum_list(head)
```
Why it fails
The call receives a list of the same size, so the problem never gets smaller and the calls never reach the empty list.
Do this instead
```
return head.value + sum_list(head.next)
```
Common mistake
Forgetting that an empty list is represented by None, so a check for an empty list must compare the head reference rather than read a value from it

Practice Tracing and Writing

EASY

Trace sum_list on a list of four nodes holding the values 1, 2, 3, and 4. Write down the value of head for each call, the value each call returns, and the order in which the calls finish. Then check your final answer.

Hints

Start by listing the calls from the outermost to the deepest, one line per call.
The deepest call returns 0. Then add each head value to the value that comes back, working upward.
The first call should return 10.

Your attempt (not saved)

MEDIUM

Write a recursive function count_nodes(head) that returns the number of nodes in a linked list. Use the same pattern as sum_list: a base case for the empty list, and a recursive case that adds 1 for the head and delegates the tail to a recursive call.