Linked lists with recursions

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:

LIST is an object of type Node* and therefore we say that it is a list.
However, by that same argument the next-field of the node with data-value 87 (colored blue below) is a list.
- Note that LIST->next is of type Node*.
- In particular, LIST->next is a list containing 42, 53, 4, i.e. everything but the first element of the list that LIST is.

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.

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)
    L = deletefront(L);
}

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

Recursive version

This gets much simpler with recursion. The logic goes like this:

If the list is empty, there's nothing to delete.
Otherwise, do:
1. Use recursion to delete all the second-to-last nodes
2. Then delete the first node.
Note the first node should be the last thing you delete (otherwise the next pointer in the first node, which has already been deleted, will be used; it will crash your program).

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.

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.


Node* add2back(string d, Node* L)
{    
  // base case: L is an empty list
  if (L == NULL)        
    return new Node{d, NULL};
  else{
    // recursive case: ask the list L->next to handle adding back the value d 
    L->next = add2back(d,L->next);
    return L;             // L still points to the first node of the list.
  }
}

Practice Problems

Find the maximum value in a list of double's.

double max_r(Node* L)
{
  if (L->next == NULL)
    return L->data;
  else
    return max(L->data,max_r(L->next));
}

Construct a copy of a list of double's. Check out a recursive solution to this problem, using add2front() function.

Recursive addinorder()

(Drag your mouse to see the code below.)

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