java - 在Java中对对象进行递归的有效方法？

Question

在使用 Java 的动态编程中，我经常希望在递归步骤中传递数组或对象作为参数。但是，为了不修改原始值，我必须在将对象作为参数传递之前克隆该对象；这样做会产生非常不利的时间和空间复杂性，因为该方法可能有数千个堆栈。我读自Is there a more efficient way passing object parameters in recursion?解决这个问题的一种可能方法是在完成计算后撤消该过程。但是，有时这是无法撤消的(例如，当递归方法从数组中删除元素时)。有人有解决这个问题的办法吗？我在竞争性编程的背景下使用它，有时自下而上的解决方案会过于复杂且不切实际。

一个例子:

public static int method(ArrayList<Integer> list) {
    if(list.size()==1) {
        return list.get(0);
    }
    ArrayList<Integer> clone = new ArrayList<>();
    for(int e:list) {
        clone.add(e);
    }
    clone.remove(clone.size()-1);
    method(clone);            
}

如果我没有克隆它而是这样做:

public static int method(ArrayList<Integer> list){
    if(list.size()==1) {
        return list.get(0);
    }
    list.remove(list.size()-1);
    method(list);            
}

原始对象将被修改。在这种情况下，显然可以只返回数组的第一个元素，而不是创建这个立方体代码。不过，我的观点是为了说明传递对象的问题。

Answer 1

对于如此普遍的问题存在答案(并理解普遍性的基本原理)，它是 persistent data structures 。这些是用于在像 Haskell 这样的语言中进行高效计算的东西，其中一切都是不可变的，并且所有算法都基于递归，因此它们当然适合您的情况。也就是说，Java 并未针对此类操作进行优化，因此您可能会发现听起来比较笨拙的解决方案在实践中编码和/或执行速度更快。