6

如下非常简单的 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));
    }
}
4

8 回答 8

6

问题是这一行：

 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变量。

于 2012-08-05T03:26:14.287 回答
3

为了给出完整的答案，我将通过这个来获得乐趣（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);
}
于 2012-08-05T04:29:59.213 回答
3

目前对这个问题的回答并没有找到问题的根源。Java中的行为是由于以下事实：

sum += fun(n - 1);

相当于：

sum = sum + fun(n - 1);

wheresum之前评估fun(n - 1)并存储该值。我们可以通过转到 JLS 部分15.26.2 看到这一点。复合赋值运算符说：

E1 op= E2 形式的复合赋值表达式等价于 E1 = (T) ((E1) op (E2))

然后评估左侧操作数，然后评估右侧操作数并执行操作。所以sum在递归的每次迭代之前被评估并且0一直返回。

这也意味着，如果您将线路切换到此：

sum = fun(n - 1) + sum ;

它会产生你想要的效果，因为fun首先会被评估。

在C++中：

sum += fun(n - 1);

也相当于：

sum = sum + fun(n - 1);

这在草案 C++ 标准部分5.17 赋值和复合赋值运算符中有所介绍，其中说：

E1 op = E2 形式的表达式的行为等价于 E1 = E1 op E2，除了 E1 只计算一次。[...]

主要的不同是左右手侧的评估顺序是未指定的，这在1.9 程序执行第15段中有所介绍，它说：

除非另有说明，否则单个运算符的操作数和单个表达式的子表达式的评估是无序的。[...]

等等1，并且8都是C++中的有效结果。我们可以看到这个 live gcc 给了我们 8而clang 给了我们 1。

于 2014-02-25T02:38:11.970 回答
1

试试这个：

public class Test {

   public static int fun(int n) {
      System.out.println("processing n " + n );

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

   public static void main(String[] arg) {
      System.out.print(fun(5));
   }
}
于 2012-08-05T03:38:30.333 回答
1 
public static int fun(int n) {
    if (n == 1)
        return 1;
    else
        return n +  fun(n - 1);
}

顺便说一句，如果您想以与 C 代码相同的方式执行此操作，只需将 sum 定义为“Integer”而不是“int”

于 2012-08-05T03:41:31.300 回答
0

你真的需要在那里逐步完成你的逻辑。这没有任何意义。是 f(5) = 8 的“奇怪”输出吗？（您实际上不小心编写了一个计算 2^(n-2) 的函数，但这似乎无关紧要）

我无法向您解释任何语法错误的地方 - 它是算法本身。它只是没有做你打算做的事情。一个重要的危险信号应该让您脱颖而出：变量 n 甚至没有直接添加到 sum 任何地方！当您调用 fun(5) 时，甚至不会使用 5。它只是传递给 f(4)。

在我看来，您的逻辑是这样的：从 n->1 递归循环，并将其添加到 sum。在这种情况下，您的功能应该是：

void fun(int n){
    if(n == 0)
        return;
    sum += n;
    fun(n-1);
}

或类似的东西。但这不是一种非常...递归的做事方式。完全没有变量你会好得多。非基本情况：返回 n+fun(n-1)。

同样在将来，当您说某些代码具有“奇怪的输出”时，您可能应该同时提供 1）奇怪的输出和 2）您期望的输出。我们都在猜测你想写什么。

于 2012-08-05T03:37:55.960 回答
0 
return n <= 1 ? n : n + fun(n-1);
于 2012-08-05T03:54:45.063 回答
0

试试这个

   static int getsum(int num){
        int sum = 0;
        if(num == 1){
            return num;

        }else{
             sum  = num+getsum(num-1);  
        }

        return sum ;
    }
于 2012-08-05T04:42:44.563 回答