Рекурсивный метод indexOf() для самодельного класса

Question

Мне присваивается список классов (здесь: http://pastebin.com/ZCi3q7LQ) и им необходимо написать некоторые методы для него, включая метод, который находит индекс для указанного целого.

Индексы начинаются с нуля, метод должен возвращать -1, если указанное число не указано в списке, метод должен работать рекурсивно и работать в $ O (n) $ time.

Моя проблема заключается в том, что метод возвращает -1 при вызове indexOf для целого числа, которое не входит в нетривиальный список. Я пробовал практически все возможные комбинации, а также прочитал некоторые похожие вопросы, но они не помогли. Это то, что я сделал:

public int indexOf(int x) { 
    return indexOf(x, first); 
} 

private static int indexOf(int x, Node n) { 
    if (n==null) { 
     return -1; 
    } 
    else if (n.data==x) { 
     return 0; 
    } 
    else return 1+indexOf(x, n.next); 
} 

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

(если это имеет значение, да это домашнее задание.)

Answer 1

Проблема заключалась в том, когда он вернулся обратно в стек он всегда добавил один к возвращаемому значению, в том числе отрицательный. Хотя было бы легко добавить проверку, чтобы узнать, есть ли возврат -1, есть более простое решение.

public int indexOf(int x) { 
    return indexOf(x, first, 0); 
} 

private static int indexOf(int x, Node n, int depth) { 
    if (n==null) { 
     return -1; 
    } 
    else if (n.data==x) { 
     return depth; 
    } 
    else return indexOf(x, n.next, depth + 1); 
} 

Answer 2

Попробуйте

if (n != null){ //make sure n isn't null 

    if (n.data == x) { 
     return index; 
    else if (n.next == null)//if the next node is null then you've reached the end of the stack without finding a match 
     return -1; 
    //else recurse and update the index 
    index++; 
    return indexOf(x, n.next, index + 1) 
    } 
} 
return -1;