如何使Java中的递归算法保持“完成的事情”？

Question

我有一个递归算法，逐个字符地逐个字符串，并解析它以创建一个树状结构。我希望能够跟踪解析器当前所处的字符索引（对于错误消息和其他任何东西一样多），但我并不热衷于实现类似于元组的处理多个返回类型的东西。

我尝试使用Integer类型，在方法外部声明并传递给递归方法，但因为它是final的，所以当我返回时，递归调用增量“被遗忘”。 （因为整数值的增量使得传值对象参考点位于一个新对象上）

有没有办法让类似的工作不会污染我的代码？

Answer 1

既然你已经发现了伪可变整数“黑客”，这个怎么样选项：

这会让你感觉做一个独立的解析器类？如果您这样做，您可以将当前状态存储在成员变量中。你可能需要考虑你将如何处理任何线程安全问题，这对于这个特定的应用程序可能是矫枉过正的，但它可能适用于你。

Answer 2

这是一种破解，但有时我使用AtomicInteger，这是可变的，做这样的事情。我也看到其中[]尺寸1的一个int在被传递的情况下

Answer 3

我使用目前的解决方案是：

int[] counter = {0}; 

，然后将其传递给递归算法：

public List<Thing> doIt (String aString, int[] counter) { ... } 

，当我想增加它：

counter[0]++; 

不是超级优雅，但它的工作原理...

Answer 4

整数是不可变的，这意味着当您将它作为参数传递时，它将创建一个副本而不是对同一项目的引用。 （explanation）。

为了获得您正在寻找的行为，您可以编写自己的类，它类似于整数只能变化。然后，将它传递给递归函数，在递归内部递增，并且在递归结束后再次访问它时，它仍将保持其新值。

编辑：请注意，使用int []数组是这种方法的变体...在Java中，数组也可以通过引用传递，而不是像原始类或不可变类那样复制。

Answer 5

说实话，我会重新编码函数，使其成为使用循环的线性算法。这样，如果你跨过一个非常大的字符串，你就没有机会用尽堆空间。此外，您不需要有额外的参数来跟踪计数。

这也可能会导致算法更快，因为它不需要为每个字符进行函数调用。

除非当然有一个特定的原因需要递归。

Answer 6

我能想到的一种可能性是将计数存储在类的成员变量中。这当然假定公众doIt方法只被一个线程调用。

另一个选择是重构公共方法来调用私人帮助器方法。私有方法将列表作为参数并返回计数。例如：

public List<Thing> doIt(String aString) { 
    List<Thing> list = new ArrayList<Thing>(); 
    int count = doItHelper(aString, list, 0); 
    // ... 
    return list; 
} 

private int doItHelper(String aString, List<Thing> list, int count) { 
    // ... 
    // do something that updates count 
    count = doItHelper(aString, list, count); 
    // ... 
    return count; 
} 

这是假设你能做的错误在公共doIt方法处理，因为count变量实际上传递回调用者。如果你需要做的是，你当然可以抛出一个异常：

public List<Thing> doIt(String aString) throws SomeCustomException { 
    List<Thing> list = new ArrayList<Thing>(); 
    int count = doItHelper(aString, list, 0); 
    // ... 
    if (someErrorOccurred) { 
     throw new SomeCustomException("Error occurred at chracter index " + count, count); 
    } 
    return list; 
} 

这是很难知道是否这将有助于不知道更多关于你的算法实际上是如何工作的。

Answer 7

您可以使用每次调用doIt方法时都会增加的静态int类变量。

Answer 8

你也可以这样做：

private int recurse (int i) { 

    if (someConditionkeepOnGoing) { 
     i = recurse(i+1); 
    } 

    return i; 
}