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

Have you stepped through the code, or better yet, "played computer" w/ a pencil and paper to trace out the execution path? Think about what's happening to `sum` on entry, and when it's recursively passed in, incremented, then added up again. — Dave Newton, Jun 06 '21 at 12:34
@DaveNewton Yep, that's what I usually do but I don't know how to make the sum of every recursive call because if I use sum it makes : 1(sum of the first) + 2(sum of the first plus recursive) and if I introduce 0 in the sum parameter it does alright but always returns 0 because the last recursive call always read that n is <1 so it returns its sum that is 0 — JamesR, Jun 06 '21 at 12:37
If runtime matters, do not implement this function recursively - the number of function calls grows exponentially in `n`. Just because you want to count the recursive nature of these sums you don't have to implement it recursively. You could, for instance, implement a loop from `0` to `n` and store the intermediate results in an array to reuse it and avoid the (exponential) redundant work. Or even better, give it a thought and formulate the sequence explicitly in `n`. — matheburg, Jun 06 '21 at 14:00

Ricola · Accepted Answer · 2021-06-06T14:35:39.673

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.

create an object containing int sum and pass the object down
create a static variable sum, so that you can modify it everywhere in your class
create an array of one element and pass it down
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];
}

Damn it, it was so easy :( , isn't there a possible way to make it with that sum parameter because the concatenation of results right? — JamesR, Jun 06 '21 at 12:39
You can pass a parameter, but it's a bit more tricky because you can't pass references to a primitive in Java (like you can do in C). I updated my answer to explain how you could do it — Ricola, Jun 06 '21 at 12:51
Thank you so much! I appreciate a lot your explanation, I didn't know the pass by value of Java — JamesR, Jun 06 '21 at 12:56
In your first example, your `else` block is superfluous. Just return 0. — WJS, Jun 06 '21 at 16:43
I agree it's not needed, but it's a matter of taste and style honestly. I usually myself don't write else branches after an early return (to minimize indentation), but I think it's a tiny bit less obvious for people who are new to programming, which I believe OP is, based on OP's question. — Ricola, Jun 06 '21 at 17:32

Code to get sums made of a fibonacci number

1 Answers1

Easy solution : return number of sums

Alternative : passing a parameter

Iterative solution