如何递归实现 get()

Question

我想知道我的 get 方法做错了什么。我在使用循环之前已经这样做了，但我似乎无法使用递归获得相同的结果。我的 size(( 方法适用于递归，但我对为什么我似乎无法让 get(( 工作感到非常困惑。有人可以给我任何关于错误的地方的指示，或者我只是混淆了代码的位置。

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;
}

Answer 1

这可能会有所帮助

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);        
}

Answer 2

你可以像我用Cell<T> class那样做。 每次increment counter然后再次调用get(idx)时，counter都将重置为0。这是因为递归发生在Stack中，并且只有一个变量称为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
}
}

如果每次递归调用innerGet(index)时都decrement index，它就可以工作。这就像增加计数器，但反过来。 我实现了innerGet(int index)因为如果你递归地调用get(int index)，由于size()方法，它有一个 O(n^2(。如果你以这种方式实现它，它是 O(n(。