SI204: Linked lists with recursions

Linked Lists 4: recursion

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 it is of type Node*.
- In particular, it is a list containing 42, 53, 4, i.e. everything but the first element of the list that LIST is.

Important:
In conclusion, one can look at a list as consisting of:

the first node and
the list of everything else.

Printing a list

To write a recursive function to print out a linked list, we can start with the template above:


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
  }
}

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! 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(Node* L) {
  return 1 + length(L->next);
}

Well, this almost works. It only "almost" work because our recursive function has no base case. On the other hand, 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

A One place recursion really "shines" with linked lists is in deleting a list. Remember the iterative version:


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

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

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. So get to work!

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. 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)
    add2front(d,L);
  else
    add2back(d,L->next);  
}

Problems

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

Recursive insertinorder()

(Drag your mouse to see the code below.)

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