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

Question

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

我尝试使用 Integer 类型，在方法外部声明并传递到递归方法中，但因为它是最终的，所以当我返回时，递归调用增量会被“忘记”。 （因为整数值的增量使按值传递的对象引用指向新对象）

有没有办法获得类似于工作的东西，而不会污染我的代码？

Answer 1

你还可以这样做：

private int recurse (int i) {

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

    return i;
}

Answer 2

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

为了获得您正在寻找的行为，您可以编写自己的类，它就像仅可变的 Integer 类。 然后，只需将其传递给递归函数，它就会在递归中递增，并且当递归结束后再次访问它时，它仍然会保持其新值。

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

Answer 3

您可以只使用一个静态 int 类变量，每次调用 doIt 方法时该变量都会递增。

Answer 4

既然您已经发现了伪可变整数“hack”，那么这个选项怎么样：

创建一个单独的解析器类对您来说有意义吗？ 如果这样做，您可以将当前状态存储在成员变量中。 您可能需要考虑如何处理任何线程安全问题，对于这个特定的应用程序来说这可能有点过分了，但它可能对您有用。

Answer 5

这是一种黑客行为，但有时我使用可变的 AtomicInteger 来做这样的事情。 我还见过传入大小为 1 的 int[] 的情况。

Answer 6

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

int[] counter = {0};

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

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

当我想增加它时：

counter[0]++;

不是超级优雅，但它有效......

Answer 7

老实说，我会重新编码该函数，使其成为使用循环的线性算法。 这样，如果您单步执行非常大的字符串，就不会耗尽堆空间。 此外，您不需要仅仅为了跟踪计数而使用额外的参数。

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

当然，除非有特定原因，否则它需要递归。

Answer 8

我能想到的一种可能性是将计数存储在类的成员变量中。 当然，这假设公共 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;
}

如果不了解更多关于算法实际工作原理的信息，很难知道这是否有帮助。