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.
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.
next
-field of the node with data-value 87 (colored blue below) is a list.
LIST->next
is of type Node*
.
LIST->next
is a list containing 42, 53, 4, i.e.
everything but the first element of the list that LIST
is.
LIST
= (the first data, i.e.,
LIST->data
) + (the list of everything else, i.e., LIST->next
)
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 That's easy too — you print out the node's data field in step 1! |
|
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
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.
double sum(Node* L)
{
if (L == NULL) {
return 0;
} else {
return L->data + sum(L->next);
}
}
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;
}
next
pointer in the first node, which has already been deleted,
will be used; it will crash your program).
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.
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); } }
double
's. Check out
my recursive and iterative solutions
double
's. Check out my recursive solution to this problem, using add2front() function.
(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); }