Geek asks and answers

Fibonacci Series - Recursive Summation

Ok, I originally wrote a simple code to return a Fibonacci number from a series based on 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 changing the code to return the amount of the series, and not just returning the value from the series, and trying to make the amount that I accidentally added 1 to the return statement, and, to my surprise, it returned the amount correctly.

The following code will return 7 for n = 5.

I'm not sure if this is the right way to calculate the amount ...

I still could not understand how the series summarizes if I add. 1. Can someone 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

Function returns 376

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

n = 10

Function returns 88

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

+5
6

fibonacci . , , . - " ", , . , n- . :

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

:

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

/ .

:

, , 1. - , ,

, , SO. , , . , . . F[i] - i- , S[n] - < n, :

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

, , S[n+2],

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

, S[n] + 1 F[n+2]:

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

, " 1 " fibonacci.

, , . F fibonacci, S " 1 " fibonacci.

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

, k > 0:

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

, , :

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

. .

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

: , k > 2, S[j+1] = F[j+1] + S[j] 0 < j < k+1 , , j = k+1, : 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]

.

+9

, . . !

, , :

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

, .

+3

- .

( , )

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;
}
+1

n<1 - 0 , ...

- fib(5), :

...
return(fib(4) + fib(3))

fib(4):
return(fib(3) + fib(2))

fib(3):
return(fib(2) + fib(1))

now fib(2) == 1 by your definition, and fib(1) == 0

so fib(3) == 1

then fib(4) == 1 + 1 = 2

and fib(5) = fib(4) + fib(3) = 2 + 1 = 3

Now if you add the '+1', the following happens:

fib(1) and fib(2) are unchanged
fib(3) = 1 + 0 + 1 = 2
fib(4) = fib(3) + fib(2) + 1 = 4
fib(5) = fib(4) + fib(3) + 1 = 4 + 2 + 1 = 7

, , "" ( , ).

0

Recursively, this is a very inefficient way to calculate the Fibonacci number. After the number 43, it will take more than 30 seconds until you get a response. I tried to figure out how long it would take to figure out number 52, and it took about 47 minutes. Thus, time is growing very fast.

Recursive code:

private int calculateRecursivelyInt(int fnum)
    {
        if (fnum == 0)
            return 0;
        if (fnum == 1)
            return 1;

        return calculateRecursivelyInt(fnum - 1) + calculateRecursivelyInt(fnum - 2);
    }

Cycles are much more efficient.

    //This method will be able to calculate till the F46 because int can't hold a 
    // bigger number. You can calculate till 92 with a type long and till 93 with
    // unsigned long in C#.

    private int calculateLoopInt(int num)
    {
        int fnum = 0;
        int val1 = 0;
        int val2 = 1;

        for (int i = 0; i < num; i++)
        {
            if (num == 1)
                fnum = 1;
            else if (i > 0)
            {
                fnum = val1 + val2;
                val1 = val2;
                val2 = fnum;
            }
        }
        return fnum;
    }
0
source

another approach to printing Fibonacci series using a recursive function.

#include <iostream>

// 0 1 1 2 3 5 8 13...
//

void fibb (int idx, int curr = 0, int next = 0)
{
        std::cout << curr << ", ";
        if(!idx) return;
        if(curr == 0) {
                curr = 1;
                fibb(--idx, curr, next);
                return;
        }
        next += curr;
        fibb(--idx, next, curr);
}


int main()
{
        fibb(10);
}
0
source

More articles:


All Articles