# IC210 Class 40: More Recursion

Review Section 13.1  of Problem Solving with C++

Lecture

This whole lecture is simply about looking at typical linked list problems and how they're solved. Both in the problem discussed in detail in the notes, and in the problems given at the end of the notes, we look at both iterative (i.e. using loops!) approaches and recursive approaches.

## A typical linked list problem - compute the length

Here's a typical example of a linked list problem: Write a function that determines the length of a linked list - i.e. the number of nodes. Assuming that we have a `Node` struct like this:

`struct Node`
`{`
`public:`
` int data;`
` Node *next;`
`};`

we know that our function's prototype should look like this:

`int length(Node*);`

It returns an `int` because, of course, the length of a list is an integer. It takes a pointer to a `Node`, because we manipulate lists by manipulating pointers, just like with arrays. The process we use to determine the length is straightforward too: move through the list from front to back one node at a time, keeping track of how many you visit in the process.

`int length(Node *L)`
`{`
`  // Initialize: curr points to the node we're about to visit`
`  Node *curr = L;`
`  int count = 0;`
` `
`  while(????)`
`  {`
`     // record that we've visited the node pointed to by curr`
`     count++;`
` `
`     // set curr to the next node to visit`
`     curr = curr->next;`
`  }`
` `
`  return count;`
`}`

The only real difficulty is going to be this: How do we know when we're done? What do we replace the `????` with? The easiest way to determine this is to work through our current function as it operates on an example list:

 Before 1st loop iteration Clearly we want to continue our iteration ... we haven't even started yet! So, `curr` gets set to `curr->next`, which leaves it pointing at the second node, and `count` gets incremented, showing that we've visited one node so far. Before 2nd loop iteration Noticing from the picture that we're pointing to the last node in the list, you might be tempted to think that we ought to stop now. However, `curr` is pointing to the node we are about to visit, not the one we just finished visiting. So, we haven't visited node 2 yet, and therefore should continue looping! Before 3rd loop iteration Now `curr` is the null pointer (i.e. pointer 0) so there's no nodes left to visit. We've visited them all, as `count` attests to, we we should exit our loop.

From the preceding example, what was it that told us when we should continue looping versus when it was time to stop? It was the value of `curr`! Specifically, as long as `curr` isn't the null pointer we should continue looping! From this, we see that our function's completed definition should be:

`int length(Node *L)`
`{`
`  // Initialize: curr points to the node we're about to visit`
`  Node *curr = L;`
`  int count = 0;`
` `
`  while(curr != 0)`
`  {`
`     // record that we've visited the node pointed to by curr`
`     count++;`
` `
`     // set curr to the next node to visit`
`     curr = curr->next;`
`  }`
` `
`  return count;`
`}`

In general this way of writing functions for manipulating linked lists is pretty good. It's usually questions like "when do we stop this loop?" or "does this work with an empty list?" that cause us problems. (Convince yourself that our `length` implementation does work for the empty list!) Try applying the same technique to the problems listed below.

## A recursive approach to functions on lists

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. 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:

So, `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 is a list. After all, isn't it also of type `Node*`? It is the list 42, 53, 4, i.e. everything but the first element of the list that `LIST` is. So, there is this natural way of looking at a list as consisting of the first node and the list of everything else.

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 == 0)`
`    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 != 0; 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. Try doing the Problems below both ways:

## Deleting a list

Since nodes in a linked list are each created dynamically with "`new`", they live on in your program until they are each individually destroyed with "`delete`". It is often useful to have a function `void deletelist(Node* L);` that deletes each of the nodes in a list. In good ol' top-down fashion, I'll implement this function "wishing" that other functions were available to me:

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

So, you see that the real problem is deleting the first node in a list.

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

Hopefully you see that `L = L->next` effectively removes the first node from `L`, but that to actually give back the memory we allocated when creating that node with `new`, we need to call `delete`.

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. An iterative solution is tougher!

3.      Construct a reverse copy of a list of `double`'s. Check out my iterative solution to this problem. A recursive solution is tougher!

Assoc Prof Christopher Brown