在递归中使用+ =的Java和C ++中的不同结果
如下非常简单的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 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)); } }
为了给出一个完整的答案,我将通过这个来获得乐趣(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); }
问题是这一行:
sum += fun(n - 1);
这是更新变量sum
。
假设您只是尝试将数字从1加到N,那么它应该进行计算,以f(N - 1)
计算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
变量。
目前这个问题的答案没有找到问题的根源。 Java中的行为是由于以下事实:
sum += fun(n - 1);
相当于:
sum = sum + fun(n - 1);
在fun(n - 1)
之前评估sum
并存储该值。 我们可以通过转到JLS第15.26.2节来看到这一点。 复合赋值运算符表示:
E1 op = E2forms的复合赋值表达式等效于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 = E2forms的表达式的行为等同于E1 = E1 op E2,除了E1仅被评估一次。[…]
主要的不同是左侧和右侧的评估顺序没有具体说明,这一点在1.9
节目执行第15段中有所说明:
除非另有说明,否则对个体经营者的操作数和个别表达的子表达式的评估是不合理的。[…]
所以1
和8
都是C ++中的有效结果。 我们可以看到这个现场gcc给了我们8 , clang给了我们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)); } }
public static int fun(int n) { if (n == 1) return 1; else return n + fun(n - 1); }
顺便说一句,如果你想以与C代码相同的方式进行,只需将sum定义为“Integer”而不是“int”
return n <= 1 ? n : n + fun(n-1);
试试这个
static int getsum(int num){ int sum = 0; if(num == 1){ return num; }else{ sum = num+getsum(num-1); } return sum ; }
你真的需要在那里逐步完成你的逻辑。 它没有任何意义。 f(5)= 8是“奇怪的”输出吗? (你实际上是不小心写了一个计算2 ^(n-2)的函数,但这似乎不是重点)
我无法向你解释任何语法错误 – 它的算法本身。 它只是不按你的意图去做。 一个很大的红旗应该是你的特点:变量n甚至不能直接添加到任何地方! 当你打电话给乐趣(5)时,甚至不使用那个5。 它刚刚进入f(4)。
在我看来,你的逻辑是这样的:递归地从n-> 1循环,并将其添加到sum。 在这种情况下,您的function应该是:
void fun(int n){ if(n == 0) return; sum += n; fun(n-1); }
或类似的东西。 但这不是一种非常……递归的做事方式。 没有任何变量你会好多了。 非基本情况:返回n + fun(n-1)。
同样在将来,当你说某些代码有“奇怪的输出”时,你应该提供1)奇怪的输出和2)你对输出的期望。 我们都在猜你想写什么。