Recursion on a linked list

A linked list is already shaped like a recursion, and noticing that makes every method below short. A list is either nothing at all, or one node followed by a list. That sentence has a base case and a recursive case in it, and it is the whole structure.

head -> [10] -> [20] -> [30] -> null
         |      \_______________/
      one node       a list, which is
                     nothing, or one node
                     followed by a list

So on a list the smaller problem is not an index. It is node.next. Every method here takes a node, answers for the empty case when that node is null, and otherwise does something with node.data and hands node.next to itself.

The shape, once

public int size()
{
    return size(this.head);
}

private int size(Node node)
{
    if (node == null)
    {
        return 0;
    }
    return 1 + size(node.next);
}

The same public and private split as on an array, and for the same reason. A caller has a list and wants a number. The recursion needs a node, and Node is a private class nobody outside can even name, so the helper has to be private.

The base case is node == null, which is the empty list, and it returns 0. Notice that the same test covers 2 situations that feel different: a list that was empty to begin with, and the end of a list you walked to. They are the same thing to this method, because null is null.

The recursive case is combine on return. It hands node.next to itself, trusts the answer, and adds 1 for the node it is standing on. Adding up the values instead of counting them changes one character.

private int sum(Node node)
{
    if (node == null)
    {
        return 0;
    }
    return node.data + sum(node.next);
}

On a list with a sentinel node at the front, the public method starts the walk at this.head.next instead of this.head, because the sentinel holds nothing worth counting or adding. Nothing about the helper changes.

Printing a list in reverse

This is the example the official topic list names, and it is the one that shows what a recursion can do that a single walk cannot.

Think about why it is hard with a loop. The chain runs one way. You can walk to the end easily enough, and then you are standing on the last node with no way to step backward, because a singly linked node has no reference to whatever came before it. Printing in reverse with a loop means either reversing the list first, or making a second structure to hold the values, or walking from the front once per position.

The recursion does it with no extra structure at all, because the call stack already remembers the order you came in.

public void printReverse()
{
    printReverse(this.head);
}

private void printReverse(Node node)
{
    if (node == null)
    {
        return;
    }
    printReverse(node.next);
    System.out.println(node.data);
}

The whole trick is the order of the 2 statements. The call comes first, so nothing prints until the recursion has run all the way to the end of the list. Every frame is parked on the line after its call, holding its own node, waiting. Then the base case returns, and the frames finish one at a time in the reverse of the order they were created, each printing the node it was holding.

Trace it on 10 20 30. The left column is the calls going down, the right column is the printing coming back.

going down
  printReverse(10)  calls next
  printReverse(20)  calls next
  printReverse(30)  calls next
  printReverse(null)  returns

coming back
  printReverse(30)  prints 30
  printReverse(20)  prints 20
  printReverse(10)  prints 10

Output: 30, 20, 10.

Move the println above the call and the same method prints 10 20 30, in order, because now every frame prints before it makes its call and the work happens on the way down. Those 2 statements in those 2 orders are forward and backward, and there is nothing else to remember.

Recursion that rewires, not just reads

Everything above reads the list and changes nothing. A recursion can also do the rewiring, and reversing a list is the standard case. Working it through makes the trust-the-smaller-call idea concrete, and it tests whether you actually believe it.

private Node reverse(Node node)
{
    if (node == null || node.next == null)
    {
        return node;
    }
    Node newHead = reverse(node.next);
    node.next.next = node;
    node.next = null;
    return newHead;
}

The base case is a list of 0 or 1 nodes, which is already reversed exactly as it stands, so it hands itself back.

Otherwise, assume the call reversed everything after node and handed back the front of that reversed piece. Now node has to be attached to the back of it. Slow down on the next sentence. node.next still points at what used to come after node, and that node is now the last node of the reversed piece. So node.next.next = node makes it point back at node, and node.next = null makes node the new end. newHead was decided once, at the very bottom of the recursion, and every frame passes it back up unchanged.

The public method finishes the job with this.head = reverse(this.head);, and that assignment is the only place head ever moves.

Where recursion on a list costs you something

One frame per node. A list of 10 nodes uses 10 frames, which is nothing. A list of a million nodes uses a million frames, and the region they live in is not that big, so it ends in a StackOverflowError. This is the reason the standard library's own list classes do their walking with loops.

At the sizes these problems use it does not come up, and the shape is what is being asked for. It is worth knowing that the trade exists, so that "use recursion" and "recursion is always the better choice" do not get filed as the same statement.

In the practice APE

The Practice APE Exam Instructions have no recursion problem on a linked list. Both recursion problems in that set are on arrays, and they are worked in Recursion on an array.

The official topic list names printing a linked list in reverse as its first example, in its own words:

Simple recursive methods to accomplish a task, which may or may not be list related. Examples would be printing a linked list in reverse, computation of factorials, and other recursive algorithms at the level of those covered in Programming Principles I and II and in Data Structures.

Official site: FAQs About the APE, item 15.

What that means for how you prepare: a list problem and a recursion problem can be the same problem. Read the file you are handed for which one it is asking for rather than which folder it sits in.

Readiness check

Work each one on paper and write the answer down before you open it.

The one thing to keep

A list is nothing, or a node followed by a list, so the base case is node == null and the smaller problem is node.next. Counting and adding put the call on the right of the operator and combine on the way back. Printing in reverse puts the call before the print, so every frame waits, and the stack hands the nodes back in the opposite order without any extra structure. Put the print first instead and the same method prints forward. A recursion that rewires trusts the smaller call for the piece it returns and only attaches the node it is standing on. One frame per node, which is free at these sizes and not free at every size.