How to implement get() recursively

Admin 1
Viewed 66

I was wondering what I am doing wrong with my get method. I've done this before using loops but I cant seem to get the same using recursion. My size() method works with recursion but I am very confused with why I can't seem to get get() to work. Can somebody give me any pointers to whats wrong or if I am just mixing up the positions of the code. 

public class Node {

    public Node previous;
    public Node next;


    public int size() {
    int count = 0;
    if (next == null) {
        count += 1;
    }
    if (next != null) {
        count = 1 + next.size();
    }
    return count; 
    }


    public Node get(int idx) { 
    int count = 0;
    if (next != null) {
        if (idx >= 0 && idx <= size()) {
            if (count == idx) {
                return next.previous;
            }
            count++;
        }
        //return get(idx);
    }
    return next.previous;
}
doubly-linked-list nodes recursion linked-list java
2 Answers

This might be helpful

public Node get(int index) {
    if (index < 0) {
        // Asked negative index. Throw exception or return null
    }
    if (index == 0) { return this; }
    if (next == null) {
        // Index out of bounds. Throw exception or return null
    }
    return next.get(index - 1);        
}
user_104540660

You can do it like I did it with my Cell<T> class. Every time you increment counter and then invoke get(idx) again, counter will be reset to 0. This is because recursion is taking place in the Stack and there is only one variable called counter.

public Cell<T> get(int index) throws IndexOutOfBoundsException {
    if (index < 0 || index >= size()) {     // index is out of bonds
        throw new IndexOutOfBoundsException();
    } else {
        innerGet(index);
    }

}

public Cell<T> innerGet(int index) {
    if (index == 0) {                       // this element is supposed to be zero
        return this;
    } else {
        return next.innerGet(--index);      // decrement the index
    }
}

If you decrement index every time you invoke innerGet(index) recursively, it works. It is like incrementing a counter, but the other way round. I implemented innerGet(int index) because if you invoke get(int index) recursively, this has an O(n^2) because of the size() method. It is O(n) if you implement it this way.

user_136747580
Related