Different results in Java and C++ using += in recursion

Question

The very simple Java code as follows has the weird output, but the same logic code in C and C++ has the right output. I try with the JDK 1.7 and JDK 1.3 (relative JRE), the weird output is always there.

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));
    }
}

The output is 1 which should be 8. Relative C/C++ code is as follows:

#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;
}

Adding test java code:

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

The problem is this line:

 sum += fun(n - 1);

which is updating the variable sum.

Assuming that you are simply trying to sum the numbers from 1 to N, then it should be doing the calculation that calculates f(N) in terms of f(N - 1). That doesn't require you to refer to sum ... and certainly it doesn't require you to update it.

(I'm being careful NOT to tell you what the answer is ... because it you will learn more if you figure it out yourself.)

---

By the way, there is nothing Java specific about the flaw in your algorithm ...

---

It is worth noting that the real issue is not to do with static versus instance variables. The real issue is that a recursive function like this shouldn't be using either kind of variable. Now in this example you can possibly get away with it, but if the recursion involves something like this: f(N) = f(N-1) + f(N-2) you are liable to find that the different call trees interfere with each other.

A more correct solution in this case is to write the method as:

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

As I said, you don't need to refer to, or update the sum variable.