2

if I enter amount of linked list is 3 : x1 = 3, x2= 1, x3=2 that print : 2 1 3(it really true) but max=2, I could not find bug, This is my code: 

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);
}
Federico klez Culloca
  • 26,308
  • 17
  • 56
  • 95
Khoa Võ Đức
  • 43
  • 5

2 Answers2

0

Your logic is wrong, since you always return the value of the first element (since l.data > max will always be true, since max is always 0 at this point).

The correct way to think of finding the max element recursively is as follows:

The max element is the max of the first element and the max of the rest of the list.

i.e.

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

So your method should look like this:

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);
}
Eran
  • 387,369
  • 54
  • 702
  • 768
  • sorry, i don't understand sysnax (? and :) i'm learning java maybe you wirting another language – Khoa Võ Đức Nov 04 '19 at 09:35
  • @KhoaVõĐức it's the ternary conditional operator. Equivalent to `if (tailMax > l.data) {return tailMax;} else {return l.data;}` – Eran Nov 04 '19 at 09:37
0

An alternative by writing an explicit tail-recursive function 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...
}
grodzi
  • 5,633
  • 1
  • 15
  • 15