Finding the 'maximum' character in a linked list Java recursively

Question

I am trying to find the "maximum" value in a linked list recursively using a helper function. I am just starting to learn about these in my class and am pretty confused. We have a custom class that defines the type Node and another function to calculate the size of the Node or linkedlist. I solved this problem when I was comparing integers, but with characters I am lost. Here is my code: '''

    static class Node {
        public Node (char item, Node next) { this.item = item; this.next = next; }
        public char item;
        public Node next;
    }

    Node first;   // this is the only instance variable,
                  // the access point to the list

    // size
    //
    // a function to compute the size of the list, using a loop
    //  an empty list has size 0
    public int size () {
        int count = 0;
        for (Node tmp = first; tmp != null; tmp = tmp.next)
            count++;
        return count; 
    }


    /*
     * maxCharacter
     * 
     * a function to compute the 'maximum' character in the list using recursion
     * You will want to create a helper function to
     * do the recursion
     * 
     * precondition: list is not empty 
     * 
     * Examples: 
     * ["ababcdefb"].maxCharacter() == 'f'
     * ["eezzg"].maxCharacter() == 'z'
     * ["a"].maxCharacter() == 'a'
     */
    public char maxCharacter () {

        return maxCharacterHelper(first, first.size());

    }

    public char maxCharacterHelper(Node first, int index) {
        char[] alpha = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
        int max = 0;
        while(index > 0 )
            max = alpha.indexOf(first.item) > max ? first.item : max;
            maxCharacterHelper(first, index-1);
        return max;
    }

''' If you could explain how I would loop through the list recursively while maintaining the greatest char I would greatly appreciate it.

Answer 1

The golden rule with recursion is "Think of the base case first, then write the recurrence".

In this case, the base is the empty list. In this case, the maximum is the last value you've seen.

The recurrence is just a call to the rest of the list with the highest value you've called.

public static MaxNode(Node n, char currentMax) {
  if (n == null) // base case, we're at the end.
    return currentMax;

  // recurrence
  return MaxNode(n.next, currentMax > n.item ? currentMax : n.item);
}

For simple ASCII values, you can treat the maximum using the > operator.