How can I find the largest element in a linked list, recursive, given the head of the node?

Question

int findLargest (ListNode *p) // -------------------------------------------------------------------------- // Preconditions: list head pointer is passed as a parameter. // Postconditions: returns the largest value in the linked list. // -------------------------------------------------------------------------- { if (p->item != NULL) { int largest = p->item; if (largest > p->next->item) ... } ... } 

Is it possible to write this recursive function by passing only a pointer as a parameter? I cannot figure out how to do this without adding additional parameters. Any ideas? I use only sequential search. Nothing unusual.

Here is the part of the class list that you will need:

  struct ListNode { ListItemType item; // A data item on the list. ListNode *next; // Pointer to next node }; // end ListNode ListNode *head; // Pointer to linked list of items. 

Mostly I am concerned about the feasibility of the problem. Can this be done only with a pointer as a parameter?

Answer 1

This is definitely possible, although I agree that recursion is not the best solution to solve this problem. In this case, non-recursive code will be easier to read (recursion), faster (overhead for calling the function), and more memory efficiency (obviously, more stack frames).

Each recursive call returns a larger value, either its value or the value from the rest of the list.

 int findLargest (ListNode *p) { int current = p->item; int next; if (p->next == NULL) { //The value at this node is obviously larger than a non-existent value return current; } else { //Recur to find the highest value from the rest of the LinkedList next = findLargest(p->next); } //Return the highest value between this node and the end of the list if (current > next) { return current; } else { return next; } } 

Recursion stops when the next element is null.

Answer 2

Although tail recursion optimization is not required by C, if you can convert it to tail recursion (and you can do a lot of work here), then when this optimization is applied, you can maintain readability, clarity and brevity of recursion with the same performance (time and space) as the best non-recursive solution.

I changed the conditions of the function a bit so that it could work in an empty list without nodes (where p is null) and in this case it returns null. This tail is recursive and requires a different parameter:

 ListNode* findLargestRecurse(ListNode* p, ListNode* largest) { // this is an implementation detail, and would not be called directly // requires that largest is not null, but p may be null if (!p) return largest; if (p->item > largest->item) largest = p; return findLargestRecurse(p->next, largest); } // preconditions: list head pointer is passed as a parameter, and may be null // postcondition: returns the node with the largest value, or null ListNode* findLargest(ListNode* p) { if (!p) return 0; // mark A, see below return findLargestRecurse(p->next, p); } 

Note that you are using the master record, findLargest, to set up the initial conditions / context for the actual recursion, findLargestRecurse.

However, I would write this tail recursion as an iterative while loop to rely less on what is currently both very specific to the compiler and generally unfamiliar in C, which is easy to do:

 // preconditions: list head pointer is passed as a parameter, and may be null // postcondition: returns the node with the largest value, or null ListNode* findLargest(ListNode* p) { ListNode* largest = 0; for (; p; p = p->next) { if (!largest || p->item > largest->item) { largest = p; } } return largest; } 

You can isolate the !largest condition from the loop by doing this beforehand, checking the base case in the same way as the first findLargest ("mark A").

And looking at it now, you may wonder why I called the recursive version shorter: it really is not for this trivial example. This is partly due to the fact that C is intended to be iterated (pay attention to the for loop in particular), somewhat because I tried to be detailed in recursion rather than dumping it as usual (so you could understand this more easily), but the rest because it is a simple problem.

Answer 3

I find that most recursive problems can be solved with a framework / pattern of thinking about:

• What information do I have now?
• What information will I receive if I make a recursive call?
• How can I combine these two to make the final result?
• (Also be sure to clearly indicate "base register".)

In this case, the answers

• value in current node
• the largest element in the "suffix" of the list that appears after this node
• hmmm, this is for you to find out
• (What should you return for an empty list? Does homework say?)

Enjoy.:)

Answer 4

I saw some code and can not refrain from adding my own ... because I really think it can be done easier :)

I believe item is a numeric type.

 #include <algorithm> // std::max #include <limits> // std::numeric_limits ListItemType findLargest(const ListNode* p) { if (p == 0) return std::numeric_limits<ListItemType>::min(); else return std::max(p->item, findLargest(p->next)); } 

As you can see, it’s much simpler, and I took the liberty of adding const , since we, of course, do not have to change the list itself!

Answer 5

Java version

 return max(head, head.value); int max(Node node, int currentMax) { if(node==null) return currentMax; if(node.value>currentMax) return max(node.next, node.value); else return max(node.next, currentMax); } 

Answer 6

If you want to return only the highest value, then yes, you have already written a lot.

 int FindLargest(ListNode* node){ if (node != NULL){ int downTheListLargest = FindLargest(node->next); if (downTheListLargest > node->item){ return downTheListLargest; } return node->item; } return //?? some max negative value } 

If you want to return a pointer to the largest node, then the parameter must be a double pointer (**), or the function must return a pointer.

 ListNode* FindLargest(ListNode* node){ if (node == NULL){ return NULL; } ListNode* downTheListLargestNode = FindLargest(node->next); if (downTheListLargestNode && downTheListLargestNode->item > node->item){ return downTheListLargestNode; } return node; } 

Indeed, there is no reason for this recursively. I suppose this is just an exercise to learn about recursion, but I think this is a bad example of learning.

Answer 7

Here is another idiomatic recursive solution similar to Matthew. Unlike its solution, this requires an empty list - perhaps the smallest element from an empty list does not make sense:

 // Precondition: list is non-empty. int find_largest(ListNode const* n) { assert(n != 0 && "find_largest requires non-empty list."); return n->next == 0 ? n->item : max(n->item, find_largest(n->next)); } 

This text is very similar to a mathematical definition using the notation "cases":

  { item(i), if i is the last node largest(i) = { { max{item(i), largest(i+1)} else. 

Answer 8

There is no need for recursion, and your example is not recursion (it would have to call itself).

This can only be done with a pointer as a parameter.

Hint: assign p to p-> next to the list advance.

Answer 9

Always interrupt recursion problems in two phases: a break state and "the rest of the problem." Start by thinking about the status of the stop. In linked lists, usually null node. But in your case, think about what happens if the given node is null. What would you return? The truth is that you need to return the maximum value no matter what, and when there are no elements in the list, there is no max element. In this case, maybe you can just assume that the list should have at least one element.

So what is the stop condition? A stop condition is when there is one element in the list; and in this case, the maximum value is the node value.

The next step is a recursive step. Suppose you have an item associated with a list. Notice how I describe the linked list: a node associated with the linked list. The maximum value is the node value if it is greater than the largest list value or the largest list value otherwise.