Find max value in linked list C++ 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. Show Recursive structure of a listSuppose 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:
Recursive structure of a list: Printing a listTo 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.
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?LengthAs 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 listOne place recursion really "shines" with linked lists is in deleting a list.Interative versionRemember 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 versionThis gets much simpler with recursion. The logic goes like this:
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 using 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. Node* add2back(string d, Node* L) { // special case: L is an empty list if (L == NULL) return new Node{d, NULL}; 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); return L; // L still points to the first node of the list. }Practice Problems
|