fibonacci series - recursive summation

Question

Ok, I initially wrote a simple code to return the Fibonacci number from the series based on the user input..

n=5 will produce 3..

static int fibonacci(int n) {
        if (n == 1)
            return 0;
        else if (n == 2)
            return 1;
        else
            return (fibonacci(n - 1) + fibonacci(n - 2));
    }

I was thinking of modifying the code to return the sum of the series rather than just returning the value from the series and while trying to do the sum I accidentally added 1 to the return statement and to my surprise, it returned the sum correctly.

The below code will return 7 for n=5.

I am not sure if this is a right way to calculate the sum...

I still couldn't figure out how the summation of the series works if I add 1. Can someone please explain??

static int fibonacci(int n) {
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        return (fibonacci(n - 1) + fibonacci(n - 2)+(1));
}

EDIT:

For Fibonacci series..0,1,1,2,3,5,8,13,21,34,55,89,144....

I tried for some random n

n=13

The function returns 376

0+1+1+2+3+5+8+13+21+34+55+89+144 = 376

n=10

The function returns 88

0+1+1+2+3+5+8+13+21+34= 88

Solution 1

Your modification to your fibonacci program does indeed work to calculate sums. However, the way you have used recursion is inefficient. One way to deal with this is with a "dynamic programming" approach, where calculated values are cached so that they can be re-used by the second recursive call. However, the n-th Fibonacci number can be forward calculated from the base. A recursive implementation of this would be:

public static int fib_r (int a, int b, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return fib_r(b, a+b, n-1);
}

public static int fib (int n) {
    return fib_r(0, 1, (n > 0) ? n : 1);
}

The corresponding code for the sum would be:

public static int sumfib_r (int a, int b, int n) {
    if (n == 1) return a;
    if (n == 2) return b;
    return sumfib_r(b, a+b+1, n-1);
}

public static int sumfib (int n) {
    return sumfib_r(0, 1, (n > 0) ? n : 1);
}

Tail recursion will often be changed by the compiler/interpreter into a simple loop as part of tail call removal.

You asked:

I still couldn't figure out how the summation of the series works if I add 1. Can someone please explain??

This question is really about understanding the algorithm, which I would suppose is topical on SO. But, math is required to describe why the algorithm works. So, this is really a math question. There is a well known theorem regarding the sum of Fibonacci numbers. If F[i] is the i-th Fibonacci number, and S[n] is the sum of the first n Fibonacci numbers, then the theorem above states:

    S[n] = F[n+2] - 1

So, if we consider that by definition of S[n+2],

S[n+2] = S[n+1] + F[n+2]

Then, substituting S[n] + 1 for F[n+2]:

S[n+2] = S[n+1] + S[n] + 1

Which you should recognize is your "add 1 modified" fibonacci function.

---

Below is a proof by induction that your program computes the sum that I provided in my original answer. Let F represent your fibonacci function, and let S represent your "add 1 modified" fibonacci function.

F[1] = 0
F[2] = 1
F[i] = F[i-1] + F[i-2] for i > 1

S[1] = 0
S[2] = 1
S[i] = S[i-1] + S[i-2] + 1 for i > 1

Then, you want a proof that for k > 0:

         k
       .---  
S[k] =  >   F[i]
       `---
       i = 1

Note that the above summation is true if and only if:

S[1] = F[1]
S[k] = F[k] + S[k-1] for k > 1

The proof is fairly straight forward. The base cases are trivially true.

S[1] = F[1] = 0
S[2] = F[2] + F[1] = 1
S[3] = S[2] + S[1] + 1 = F[3] + F[2] + F[1] = 2

The induction step is: Given that for some k > 2, S[j+1] = F[j+1] + S[j] for 0 < j < k+1, prove that the equality holds true if j = k+1, that is: S[k+2] = F[k+2] + S[k+1].

    S[k+2] = S[k+1] + S[k] + 1
=>  S[k+2] = (F[k+1] + S[k]) + (F[k] + S[k-1]) + 1
=>  S[k+2] = (F[k+1] + F[k]) + (S[k] + S[k-1] + 1)
=>  S[k+2] = F[k+2] + S[k+1]

This completes the proof.

Solution 2

No it won't. The second version of the code does not compute the sum of all the values of the fibonacci function up to the given value. And the base cases are wrong, too!

If you want to calculate the sum recursively, split the problem in two parts, like this:

public static int fib(int n) {
    return n < 2 ? n : fib(n-1) + fib(n-2);
}

public static int sumfib(int n) {
    return n < 0 ? 0 : fib(n) + sumfib(n-1);
}

The first function calculates fibonacci, the second takes care of adding the values up to a given number.

Solution 3

The right way to do it is use accumlator.

the code should look something like this (i didn't check it, it's only the idea)

static int fibonacci(int n, int accumlator) {
    if (n == 1)
        return 0;
    else if (n == 2)
        return 1;
    else
        accumlator = (fibonacci(n - 1, accumlator) + fibonacci(n - 2, accumlator));
        return accumlator;
}