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.
Node*
.
LIST
is.
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.
And the answer is, nothing! So we can leave that part blank in the code.
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
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.
double sum(Node* L) {
if (L == NULL) {
return 0;
} else {
return L->data + sum(L->next);
}
}
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:
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. So get to work!
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); }
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 insertinorder(double val, Node* &L) { if( L == NULL || val < L->data ) add2front(val,L); else insertinorder(val,L->next); }