CODEWITHSUNDEEP
javarecursionmethodslinked-listnodes
jaaj
jaaj

Reputation: 17

Finding the maximum value of a linked list recursively

I need to write a Java method called findMax within a class called Node, which has two instance variables: int value and Node next. The method takes no parameters, and must return the greatest value of a linked list. Within the context of the program, the method will always be called by the first Node of a linked list (except for the recursive calls). I was struggling to complete the method when I accidentally found a working solution:

public int findMax(){
    int max = value;
    if(next == null){
        return max;
    }
    else{
        if(max <= next.findMax()){
           max = next.value;
        }
        else return max;
    }
    return next.findMax();
}

This method properly returned the largest value of each linked list I tested it for. However, since I found this solution by trying random arrangements of code, I don't really feel like I understand what's going on here. Can anyone explain to me how/why this works? Also, if there is a more efficient solution, how would it be implemented?

Upvotes: 1

Views: 15659

Answers (1)

muzzlator
muzzlator

Reputation: 742

You can imagine a linked list looking something like this:

val1 -> val2 -> val3 -> null

Recursion works on the principle that eventually, the input you pass into the function can be handled without recursing further. In your case, node.findMax() can be handled if the next pointer is null. That is, the max of a linked list of size 1 is simply the value (base case of the recursion), the max of any other linked list is the max of the value of that node or the max of the remaining elements.

ie) for the Node n3 with value val3, n3.findMax() simply returns the value

For any other node n, n.findMax() returns the maximum of the node's value or n.next.findMax()

The way this looks in the example at the start is:

n1.findMax()
  = Max(n1.value, n2.findMax())
  = Max(val1, Max(n2.value, n3.findMax())
  = Max(val1, Max(val2, n3.value)) // Since n3.next == null
  = Max(val1, Max(val2, val3))

which is simply the maximum over the whole list

Edit: Based on the discussion above, although what you said might work, there is a simpler way of writing the program:

int findMax() {
    if (this.next == null) {
        return this.value;
    } else {
        return Math.max(this.value, this.next.findMax());
    }
}

Edit 2: A break down of why your code works (and why it's bad):

public int findMax(){
    // This variable doesn't serve much purpose
    int max = value;
    if(next == null){
        return max;
    }
    else{
        // This if condition simply prevents us from following
        // the else block below but the stuff inside does nothing.
        if(max <= next.findMax()){
           // max is never used again if you are here.
           max = next.value;
        }
        else return max;
    }
    // We now compute findMax() again, leading to serious inefficiency
    return next.findMax();
}

Why is this inefficient? Because each call to findMax() on a node makes two subsequent calls to findMax() on the next node. Each of those calls will generate two more calls, etc.

The way to fix this up is by storing the result of next.findMax() like so:

public int findMax() {
    if (next == null) {
        return value;
    }
    else {
        int maxOfRest = next.findMax();
        if(value <= maxOfRest) {
            return maxOfRest;
        }
        else return value;
    }
}

Upvotes: 3

Related Questions