在递归中使用+ =的Java和C++中的不同结果

Question

如下非常简单的Java代码具有奇怪的输出,但C和C++中的相同逻辑代码具有正确的输出.我尝试使用JDK 1.7和JDK 1.3(相对JRE),奇怪的输出始终存在.

public class Test {

    public static int sum=0;

    public static int fun(int n) {

        if (n == 1)
            return 1;
        else
            sum += fun(n - 1);  // this statement leads to weird output
        // { // the following block has right output
        //     int tmp = fun(n - 1);
        //     sum += tmp;
        // }

        return sum;
    }

    public static void main(String[] arg) {
        System.out.print(fun(5));
    }
}

输出为1,应为8.相对C/C++代码如下:

#include<stdio.h>
int sum=0;
int fun(int n) {

        if (n == 1)
            return 1;
        else
            sum += fun(n - 1);

        return sum;
    }

int main()
{
    printf("%d",fun(5));

    return 0;
}

添加测试java代码:

class A {
    public int sum = 0;

    public int fun(int n) {
        if(n == 1) {
            return 1;
        } else {
            sum += fun(n - 1);
            return sum;
        }
    }
}

public class Test {
    public static void main(String arg[]){
        A a = new A();
        System.out.print(a.fun(5));
    }
}

Answer 1

问题是这一行:

 sum += fun(n - 1);

这是更新变量sum.

假设你只是试图从1求和号码N,那么它应该做的是计算的计算f(N)来讲f(N - 1).这不要求你参考sum......当然它不需要你更新它.

(我小心不要告诉你答案是什么......因为如果你自己弄明白的话,你会学到更多.)

顺便说一句,没有Java特定的算法中的缺陷......

值得注意的是,真正的问题与静态变量和实例变量无关.真正的问题是像这样的递归函数不应该使用任何一种变量.现在在这个例子中你可以逃脱它,但如果递归涉及这样的事情:f(N) = f(N-1) + f(N-2)你很容易发现不同的调用树相互干扰.

在这种情况下更正确的解决方案是将方法编写为:

int fun(int n) {
    if (n == 1)
        return 1;
    else
        return n + f(n - 1);
}

正如我所说,您不需要引用或更新sum变量.

Answer 2

为了给出一个完整的答案，我将为了好玩（3）而运行这个过程。对于那些不感兴趣为什么这适用于 C++ 但不适用于 Java 的人，请忽略我的回答。

这是 Java 正在做的事情：

里面的乐趣(3)

sum += sum + fn(n-1) // sum is 0

变成

sum = 0 + fun(2) // sum is 0

然后里面的乐趣（2）

sum = 0 + fun(1) // sum is 0

然后里面的乐趣(1)

return 1 // sum is 0

回到乐趣（2）

sum = 0 + 1; // sum is 0

变成

sum = 1; // sum will soon become 1

回到乐趣(3)

sum = 0 + 1; // sum is 1

变成

sum = 1; // sum gets reset to 1

这是 C++ 正在做的事情：

里面的乐趣(3)

sum += fn(n-1) // sum is 0

变成

sum = sum + fn(2) // sum is 0

然后里面的乐趣（2）

sum = sum + fn(1) // sum is 0

然后里面的乐趣(1)

return 1 // sum is 0

回到乐趣（2）

sum = sum + 1 // sum is 0

成为

sum = 0 + 1 => sum = 1 // sum will soon become 1

回到乐趣(3)

sum = sum + 1 // sum is 1

成为

sum = 1 + 1 // sum will soon become 2

你应该做什么： 我不知道为什么 C++sum在函数调用之后而不是之前进行计算。我不知道这是否在规格中。但我确实知道您不应该在任何语言中依赖于此。正确的解决方案是：

int fun(int n) {
    if (n == 1)
        return 1;
    else
        return n + f(n - 1);
}