Добрый вечер. Не могу понять действия рекурсивной функции при нахождении числа Фибоначчи.
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) и так далее?
Тут все просто - только не пользуйтесь на практике: 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)
. Все.
Во-первых, числа Фибоначчи вычисляются для неотрицательных чисел, поэтому параметр следует объявить по крайней мере как имеющий тип 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;
}
Вывод данной программы выглядит следующим образом
0: 0
1: 1
2: 1
3: 2
4: 3
5: 5
6: 8
7: 13
8: 21
9: 34
Рекурсивный вызов функции можно представить следующим образом
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 )
равно (будем использовать симметричный обход дерева)
( 0 + 1 ) + ( 1 + ( 0 + 1 ) ) == 3
Выделенный сервер, что это, для чего нужен и какие характеристики важны?
Современные решения для бизнеса: как облачные и виртуальные технологии меняют рынок
Виртуальный выделенный сервер (VDS) становится отличным выбором
Пытаюсь с QByteArray получить указатель на данные с помощью data(), ругается:
Стоит ли повсеместно стараться как можно чаще использовать r-value ссылки? Вот, допустим, код:
Доброе время суток! У меня есть проект на Python35, а именно система автоматического тестирования для локальной сети(тестер для олимпиадных задач...