Let’s look at a concrete example of a recursive function for linked lists. To do this, we will use a simple singly linked list class that only stores integers. The list itself will just have a head pointer (no size or tail). The code for the class can be found in Listing 28.14.1
The class declares a function int SimpleLinkedList::getTotal(); that returns the sum of all the integers in the list. We will start by examining it. The member function itself is not recursive. It simply calls a helper function, passing it the head pointer of the list.
In the base case, we are in charge of an empty list. In this case, the sum of the integers is zero. So, if the pointer passed to the helper function is nullptr, we return zero.
In the general case, we are responsible for a single integer. We don’t know what the rest of the list contains. It is somebody else’s problem. However, we do know that if someone tells us the sum of the rest of the list, we can add our integer to that sum to get the total for the entire list we are responsible for:
int recursiveGetTotal(ListNode* current) {
if(current == nullptr) {
return 0;
}
else {
int restOfListTotal = recursiveGetTotal(current->next);
int total = current->data + restOfListTotal;
return total;
}
}
Note28.9.1.
The recursive function is not a member function of the class. We could make a recursive member function, but this implementation helps keep the recursion logic separate from the class interface. Any particular recursive call should only know about the pointer it was given and not the head of the list or any other details that pertain to the entire list.
The implemented code has extra debugging output to help understand the recursion process. In it, we can see that we start by asking the 6 node for the total. It then asks the 10 node for the total. The 10 node asks the 3 node for the total. The 3 node asks it’s next (a nullptr) for the total. That if our base case and we return 0. That gets back to the 3 node, which adds its value (3) to 0 and returns 3. The 10 node adds its value (10) to 3 and returns 13. The 6 node adds its value (6) to 13 and returns 19. Finally, the original call to getTotal receives this total and returns it to main.
The toString function is doing almost the same job as getTotal (only building up a string). However, the implementation shows the alternate base case where we test to see if we are at the last node in the list (its next pointer is nullptr).
//Assumes there is at least one node to work with
string recursiveToString(ListNode* current) {
if(current->next == nullptr)
return to_string(current->data);
string rest = recursiveToString(current->next);
string result = to_string(current->data) + " " + rest;
return result;
}
Because of this assumption, the member toString function needs to handle the empty list case itself before calling the helper function:
Remember that “oops I went too far” is often a simpler base case than looking to see if there really is another node. Our toString function would not have to worry about the empty list case if the recursive function used nullptr as the base case.
However, there are algorithms where “next points to nullptr” is the appropriate base case. Consider the case of getting the largest value in a list. If we use nullptr as the base case, what would the return value be? We wouldn’t want to return 0, as that would produce the wrong largest value for a list like {-2, -5, -1}. Another clue that nullptr would be an awkward based case is that it isn’t clear how we should handle an empty list. What is the largest value in an empty list?
In this case, using “this is the last node” as the base case would be more appropriate. If you are responsible for just the last node, finding the largest value just means returning the data in that node. If you are responsible for some other node, you will return the largest of either the node you are responsible for or the largest value from the rest of the list. The empty list case will be handled outside the recursive function (presumably by throwing an exception or some other indication that there is an error).
