How can I find the largest item in a linked list recursively given the head 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 passing only a pointer as a parameter? I can't figure out how to do this without adding more parameters. Any ideas? I am only using sequential search. Nothing fancy.

Here is the portion of class List that will be needed:

    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.

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

Answer 1

I find that most recursive problems can be solved using the framework/template of thinking about:

• What information do I have at hand right now?
• What information will I get if I make a recursive call?
• How can I combine those two to make a final result?
• (Also, be sure to be clear about the 'base case'.)

In this case, the answers are

• the value in the current node
• the largest element in the 'suffix' of the list that comes after this node
• hmmm, that's for you to figure out
• (What should you return for the empty list? Does the homework say?)

Have fun. :)

Answer 2

If you are looking to return just the largest value, then yes you pretty much already have it written.

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 are looking to return a pointer to the largest node, then the parameter needs to be a double pointer (**), or the function needs to 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;
}

Really there is no reason to do this recursively. I assume this is just an exercise to learn about recursion, but I feel it is a poor learning example.

Answer 3

No need for recursion, and your example isn't recursion (it would have to call itself).

It is possible to do this with only a pointer as a parameter.

Hint: Assign p to p->next to advance through the list.

Answer 4

This is definitely feasible, although I agree that recursion is not the best solution to solve this problem. In this case, non-recursive code would be easier to read (recursion), faster (overhead of function call), and more memory efficient (obviously more stack frames).

Each recursive call returns the greater of either it's 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 item is null.

Answer 5

Always break recursion problems into two steps: the stop condition and "the rest of the problem". Start by thinking about the stop condition. In linked lists it's usually the null node. But in your case, think what happens when the given node is null. What would you return? The truth is that you have to return the max 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 a list must therefore have at least one element.

So what's the stop condition? The stop condition is when there's a single element in the list; and in this case the max value is that node's value.

The next step is the recursive step. Suppose you have an element linked to a list. And pay attention how I describe a linked list: a node linked to a linked list. The max value is the value of that node if it's larger than the largest value of the list, or the largest value of the list otherwise.

Answer 6

Though tail-recursion optimization isn't required by C, if you can transform it into tail-recursion (and you can without a lot of work here), then, when that optimization is applied, you can maintain the readability, clarity, and conciseness of recursion with the same performance (time and space) as the best non-recursive solution.

I've slightly modified the function's conditions so it can work on an empty list with no nodes (where p is null) and will return null in that case. This is tail-recursive, and does require another 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);
}

Notice you use the main entry, findLargest, to setup the initial conditions/context for the actual recursion, findLargestRecurse.

However, I'd write that tail-recursion as an iterative while loop to rely less on what's currently both very compiler-specific and generally unfamiliar in C, which is not hard 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 separate out the !largest condition from the loop by doing it beforehand, by checking a base case just like the first findLargest does ("mark A").

And looking at this now, you may wonder why I called the recursive version more concise: it really isn't for this trivial example. That's partially because C is designed to favor iteration (notice the for loop in particular), somewhat because I tried to be verbose in the recursion instead of squashing it down as I would normally (so you could understand it easier), and the rest is because this is just a simple problem.

Answer 7

I have seen some code posted and could not refrain to add my own... because I really think it could be done more simply :)

I suppose that item is of 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, much simpler, and I took the liberty to add a const since we're certainly not going to have to modify the list itself!

Answer 8

Here’s another idiomatic recursive solution, similar to Matthieu’s. Unlike his solution, this one requires an empty list – arguably, taking the smallest item of an empty list isn’t a meaningful operation:

// 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 one reads much like a mathematical definition, using the “cases” notation:

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