java - 线性递归如何工作？

Question

我编写了一个 java 程序，使用线性递归在数组中添加元素。获得的输出不符合预期。谁能指出这个程序有什么问题？

public class TestSum {

    public int count = 0;


    public int sum(int[] a){

        count++;

        if(a.length == count){
            return a[count -1];
        }

        return sum(a) + a[count -1] ;
    }

    public static void main(String[] args) {

        int[] a = {1,2,3};

        int val = new TestSum().sum(a);
        System.out.println(val);
    }

}

我期望输出为 6，但得到的是 9。怎么了？

奇怪的是，如果我改变加法的顺序，即 return a[count -1] + sum(a); 那么它的输出为 6。

Answer 1

一般来说，不可重入(即依赖于外部状态)的递归程序是可疑的。在您的特定情况下，count 将在 sum 的调用之间发生变化，使行为难以追踪，并最终导致您观察到的错误。

您应该将索引与数组一起传递以使其工作:

// The actual implementation passes the starting index
private static int sum(int[] a, int start){
    if(a.length == start){
        return 0;
    }
    return sum(a, start+1) + a[start];
}
// Make sure the method can be called with an array argument alone
public static int sum(int[] a) {
    return sum(a, 0);
}

与在方法外部递增计数的实现不同，此实现可以在多个线程上同时调用而不会中断。