я хочу найти максимальный узел в связанном списке по алгоритму рекурсии, но мой код имеет проблемы

Question

если я введу количество связанного списка, равное 3: x1 = 3, x2 = 1, x3 = 2, которые напечатают: 2 1 3 (это действительно так), но max = 2, я не смог найти ошибку, это мой код:

int max(Node l){
    int max = 0;
    if(l == null) return 0;
    else
    {
        if(l.data > max){
            max = l.data;
            l = l.next;
        }                 
        else return max(l.next);
    }
    return max;
}
int max(){
    return max(head);
}

Answer 1

Альтернатива, написав явную хвостовую рекурсивную функцию max

int max(Node l, int maximum)
{
    if(l == null) 
        return maximum;
    else {
        return max(l.next, l.data > maximum? l.data: maximum);
    }
}

int max(){
    return max(head, 0);//something small...
}

Answer 2

Ваша логика неверна, поскольку вы всегда возвращаете значение первого элемента (поскольку l.data > max всегда будет true, поскольку max всегда 0 в этой точке).

Правильный способ рекурсивного нахождения элемента max заключается в следующем:

Элемент max - это максимум первого элемента и максимум остального списка.

, т. Е.

max(l) is the max of l.data and max(l.next)

Итак, ваш метод должен выглядеть следующим образом:

int max(Node l)
{
    if(l == null) 
        return 0;
    else {
        int tailMax = max(l.next);
        return tailMax > l.data ? tailMax : l.data;
    }
}

int max(){
    return max(head);
}