Разбор рекурсии числа ряда Фибоначчи

245

26 ноября 2016, 19:01

Добрый вечер. Не могу понять действия рекурсивной функции при нахождении числа Фибоначчи.

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

В функции f(n-1) после "прохождения" компилятором всех значений переменной n (от 6 до 3), в f(2) возвращаемым значением является единица. Вопрос: как ЭТО возвращаемое значение влияет на следующее действие, то есть действие с f(3), затем возвращаемое значение f(3) на f(4) и так далее?

Answer 1

Тут все просто - только не пользуйтесь на практике: f(50) не дождетесь...

Формула какая? f(n) = f(n-1)+f(n-2). Это определение чисел. Далее, f(1)==f(2)==1. Все.

А для примера посчитаем

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

f(4) вызывает f(3) и f(2), f(3) - f(2) и f(1):

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

f(3) в левой части опять вызовет f(2) и f(1). А они уже не вызывают никого, возвращая 1. Идем назад:

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

Вернулись к f(5). Все.

Answer 2

Во-первых, числа Фибоначчи вычисляются для неотрицательных чисел, поэтому параметр следует объявить по крайней мере как имеющий тип unsigned int.

Функцию можно написать короче. Например

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

Вывод данной программы выглядит следующим образом

Рекурсивный вызов функции можно представить следующим образом

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

Или можно представить в виде дерева, где листья будут вызовами для функции с аргументами 0 или 1, так как эти вызовы более не вызывают функцию рекурсивно

                                       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

Если просуммировать, например, для левой ветки, начинающейся с числа 4, то получим, что Fibonacci( 4 ) равно (будем использовать симметричный обход дерева)