It turns out that a lot of linked list operations are very easily accomplished with recursion. The reason for this is that there is an essentially recursive way of looking at lists. Recall that "a list" in our program is really a pointer to the first node in a linked list.

Recursive structure of a list

Suppose LIST is a variable of type Node* in our program, and suppose that it points to the list 87, 42, 53, 4 as illustrated in the following picture:

Recursive structure of a list:
A list LIST = (the first data, i.e., LIST->data) + (the list of everything else, i.e., LIST->next)

Printing a list

To write a recursive function to print out a linked list, we can start with the template below, and then fill in the two comment lines.
Base case
First we have to answer the question, "What should happen in the base case?" Another way of putting that is, "What should happen when we try to print an empty list?"

And the answer is, nothing! So we can leave that part blank in the code.

Recursive case
The second question is, "What do we do for each node in the list?"

That's easy too — you print out the node's data field in step 1!


void printlist(Node* L) 
{
  if (L == NULL) {
    // base case:
    //    depends on what you're doing
  } else {
    // recursive case:
    // step 1: Do something with L->data before the recursion

    // step 2: Recursion
    printlist(L->next);

    // step 3: Do something with L->data after the recursion
  }
}


This gives us the complete function:

void printlist(Node* L) {
  if (L == NULL) {
    // printing an empty list - nothing to do here!
  } else {
    cout << L->data << " ";
    printlist(L->next);
  }
}
See what I mean when I said that recursion can be really "natural" with linked lists?

Length

As far as the length problem is concerned, we see that the length of LIST is one plus the length of the list given by the first node's next pointer. So can't we say:

int length_flawed(Node *L)
{
  return 1 + length(L->next);
}
Q. What is the problem with the above function?
A:  No base case 
Still, this almost works. With every recursive call the list we look at is smaller and smaller. So we're naturally working towards the base case of a list of zero elements - the empty list! Therefore, a complete recursive function for computing the length of a list is:

int length(Node *L)
{
  if (L == NULL)
    return 0;
  else
    return 1 + length(L->next);
}
That's pretty elegant. Compare that to the "slick" way of doing length iteratively:

int length(Node *L)
{
  int count = 0;
  for(Node *p = L; p != NULL; p = p->next)
    count++;
  return count;
}
Which one you prefer is a matter of taste. However, there are some situations where the iterative approach is more natural and some where the recursive approach is more natural.

Quick check

Write a recursive function that sums all the values in the list (drag your mouse to see the code below):
double sum(Node* L)
{ 
  if (L == NULL) {
    return 0;
  } else {
    return L->data + sum(L->next);
  }
}

Deleting a list

One place recursion really "shines" with linked lists is in deleting a list.

Interative version

Remember the iterative version:

void deletelist(Node* L)
{
  while(L != NULL)
    deletefront(L);
}

void deletefront(Node*& L) // Assumes L is not the empty list!!
{
  Node* T = L;
  L = L->next;
  delete T;
}

Recursive version

This gets much simpler with recursion. The logic goes like this: This leads to the following simple recursive function to delete a linked list:

void deletelist(Node* L)
{
  if (L == NULL) return;  // If the list is empty, there is nothing to delete

  deletelist(L->next);    // Use recursion to delete all the second-to-last nodes

  delete L;               // Then delete the first node
}
Let me again emphasize that the purpose of recursion is not just to have shorter, more "elegant" functions (although that's nice), it's to get comfortable with multiple ways of programming so that you have more options available when solving a new problem.

Sometimes recursion seems "better" for the problem at hand, and sometimes a loop is a more natural solution. But remember that, since you're more used to writing loops now, you won't get a good feel for this until you've written many small recursive functions.

Recursive add2back()

We can also view add2back recursively using addfront() and addafter().

Adding to the back of list L is actually the same as adding to the back of list L->next Moreover, if L is empty, adding to the back is the same as adding to the front. Those two observations give us the following recursive formulation which, I hope you'll admit, is really beautiful!

(Drag your mouse to see the code below.)

void add2back(string d, Node*& L)
{
  if (L == NULL)        
  {
    // base case: L is an empty list
    add2front(d,L);
  }
  else if (L->next == NULL)
  {
    // base case: L points to the last node, so L->next is NULL
    addafter(d, L);
  }
  else
  {
    // recursive case: ask the list L->next to handle adding back the value d 
    add2back(d,L->next);  
  }
}

Problems

  1. Find the maximum value in a list of double's. Check out my recursive and iterative solutions
  2. Construct a copy of a list of double's. Check out my recursive solution to this problem, using add2front() function.
  3. Recursive addinorder()

    (Drag your mouse to see the code below.)

    void addinorder(double val, Node*& L)
    {
     if( L == NULL || val < L->data )
       add2front(val, L);
     else if ( L->next == NULL || val < L->next->data )
       addafter(val, L);
     else
       addinorder(val,L->next);
    }