Good evening. I can not understand the actions of the recursive function when finding the Fibonacci number.

int f(int n) { if (n==1 || n==2) return 1; if (n==0) return 0; return f(n-1)+f(n-2); } int main() { cout<<f(6)<<endl; return 0; }

In the function f (n-1), after the compiler passes all the values ​​of the variable n (from 6 to 3), in f (2) the return value is one. Question: how does the IT return value affect the next action, that is, the action with f (3), then the return value f (3) to f (4) and so on?

  • 2
    in the if (n==1::n==2) string, explicitly || instead of :: . And yes, for such a code I would tear off my hands ... So you can write only in a small number of languages ​​that are optimized. - pavel

2 answers 2

Everything is simple - just do not use in practice: f(50) do not wait ...

What formula? f(n) = f(n-1)+f(n-2) . This is the definition of numbers. Further, f(1)==f(2)==1 . Everything.

And for an example we will count

 f(5) = f(4) + f(3)

f(4) calls f(3) and f(2) , f(3) - f(2) and f(1) :

 f(4) = f(3) + f(2); f(3) = f(2) + f(1);

f(3) on the left will call f(2) and f(1) again. And they no longer call anyone, returning 1. Go back:

 f(3) = 1+1 = 2; f(4) = 2+1 = 3; f(5) = 3+2 = 5;

Returned to f(5) . Everything.

    First, Fibonacci numbers are calculated for non-negative numbers, so the parameter should be declared at least as having an unsigned int type.

    The function can be written shorter. for example

     #include <iostream> unsigned int fibonacci( unsigned int n ) { return n < 2 ? n : fibonacci( n - 2 ) + fibonacci( n - 1 ); } int main() { const unsigned int N = 10; for ( unsigned int i = 0; i < N; i++ ) { std::cout << i << ": " << fibonacci( i ) << std::endl; } return 0; }

    The output of this program is as follows.

     0: 0 1: 1 2: 1 3: 2 4: 3 5: 5 6: 8 7: 13 8: 21 9: 34

    The recursive function call can be represented as follows.

     fibonacci( 6 ) = fibonacci( 5 ) + fibonacci( 4 ) fibonacci( 5 ) = fibonacci( 4 ) + fibonacci( 3 ) fibonacci( 4 ) = fibonacci( 3 ) + fibonacci( 2 ) fibonacci( 3 ) = fibonacci( 2 ) + fibonacci( 1 ) fibonacci( 2 ) = fibonacci( 1 ) + fibonacci( 0 ) fibonacci( 1 ) = 1 fibonacci( 0 ) = 0

    Or you can think of it as a tree, where the leaves will be calls to a function with arguments 0 or 1, since these calls no longer call the function recursively.

      6 ------------------------------------------ | | 4 + 5 ------------------- ------------------- | | | | 2 + 3 3 + 4 --------- --------- --------- --------- | | | | | | | | 0 + 1 1 + 2 1 + 2 2 + 3 ----- ----- ----- ----- | | | | | | | | 0 + 1 0 + 1 0 + 1 1 + 2 ----- | | 0 + 1

    If we sum up, for example, for the left branch, starting with the number 4, then we get that Fibonacci( 4 ) is equal (we will use a symmetric tree walk)

     ( 0 + 1 ) + ( 1 + ( 0 + 1 ) ) == 3