Code to get sums made of a fibonacci number

Question

I'm trying to make a simple recursive code that counts the sums of a fibonacci progression but I don't know how to make the counter works properly, this is my code:

public static long fibonacciRecursiveHits(int n,long sum) 
{
    if (n>1)
    {
        sum++;
        sum =  fibonacciRecursiveHits(n-1,sum) + fibonacciRecursiveHits(n-2,sum);
    }
    return sum;
}

Example:

Input: 4
Correct Output: 4 //The number of sums
My Output: 12

Answer 1

Your problem is that you are computing the number of sums for n AND you are adding it to the sums of n+1 and n+2 which make you count them more than once.

Easy solution : return number of sums

Just count the number of sums for n without passing them down. Try this for example:

public static long fibonacciRecursiveHits(int n)
{
    if (n>1)
    {
        return  fibonacciRecursiveHits(n-1) + fibonacciRecursiveHits(n-2) + 1;
    } else {
        return 0;
    }
}

What we are doing here : if n > 1, we count all the sums for n-1 plus the sums for n-2 plus this sum (1 sum).

Alternative : passing a parameter

If you want to pass the sum down as a parameter and update it recursively, you could, but not without a trick since Java is pass-by-value, which means if you modify sum in your function, it won't be modified for the caller. There are several ways to workaround this.

1. create an object containing int sum and pass the object down
2. create a static variable sum, so that you can modify it everywhere in your class
3. create an array of one element and pass it down
4. Other ways described in this answer

Here is an example on how to do it with option 3:

public static void fibonacciRecursiveHits(int n, long[] sum)
{
    if (n>1)
    {
        sum[0]++;
        fibonacciRecursiveHits(n-1, sum);
        fibonacciRecursiveHits(n-2, sum);
    }
}

What happens is that every call that does make a sum will increment sum.

Now you call it this way:

    long[] sum = {0};
    fibonacciRecursiveHits(4, sum);
    System.out.println(sum[0]); //sum[0] contains your result

Iterative solution

The problem of the recursive solutions above is that they have exponential running time O(2^n), which mean that would be very slow on medium to large inputs. An alternative is to build the results iteratively and keep them on an array (dynamic programming). This reduces the runtime to O(n).

public static long fibonacciRecursiveHits(int n)
{
    long[] sums = new long[n+1];
    // sums[0] and sums[1] are both initialized to 0
    for(int i = 2; i <= n; i++){
        sums[i] = sums[i-2] + sums[i-1] + 1;
    }
    return sums[n];
}