Числа Фибоначчи

Рассмотрим общеизвестный ряд чисел A000045:
[latex]0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, \ldots[/latex] Этот ряд представляет собой неотрицательную ветвь последовательности Фибоначчи. Будем считать, что последовательность задаётся следующим рекуррентным соотношением
[latex]f_n=\left\{\begin{matrix}
0, & n=0\\
1, & n=1\\
f_{n-1}+f_{n-2}, & n>1
\end{matrix}\right.[/latex]

Давайте напишем функцию, которая вычисляет [latex]n[/latex]-е по порядку число Фибоначчи, используя приведенное соотношение:

#include <cmath>
#include <iostream>
using namespace std;

unsigned long long f (unsigned short n) {
    return n < 2? n : f(n-1) + f(n-2);
}

int main() {
    cout << f(6);
    return 0;
}

#include <cmath>

#include <iostream>

using namespace std;

unsigned long long f (unsigned short n) {

return n < 2? n : f(n-1) + f(n-2);

}

int main() {

cout << f(6);

return 0;

}

Для теста мы вывели на печать вычисленное этим способом 6-е по порядку число Фибоначчи. Программа напечатала 8. И не ошиблась. Давайте посмотрим как происходили вызовы функций:

Порядок вызовов при вычислении шестого по счёту числа Фибоначчи по прямому рекурсивному алгоритму

Легко видеть, что для вычисления каждого числа Фибоначчи (кроме двух первых) выполняется строго два вызова функции. Т.е. если нам понадобится вычислить, следующее (седьмое) число Фибоначчи, то количество вызовов практически удвоится. И действительно, каждое следующее число вычисляется вдвое дольше, чем предыдущее. При наличии терпения ещё можно как-то дождаться конца вычисления 50-го числа, но дальше вычисляется уж очень долго.
В чём причина? Почему человек, вычисляя на листе бумаги, легко обгоняет компьютер?
Конечно, неэффективный алгоритм.
На рисунке цветом выделены те блоки, вычисление которых действительно необходимо. Число таких блоков растёт с увеличением номера числа линейно, говорят [latex]O\left( n\right)[/latex]. А вот остальные блоки — сплошные повторы и их число растёт как [latex]O\left( 2^n\right)[/latex].
Попробуйте изменить программу так, чтобы она работала быстро (без повторных вычислений.
В качестве упражнения, я попрошу не использовать циклов.
После того, как у Вас всё получится (или окончательно опустятся руки), загляните под спойлер и постарайтесь разобраться с моим вариантом решения задачи.

Рекурсивное решение без повторов

#include <iostream>
using namespace std;

unsigned long long tomorrow (
		unsigned short n, 
		unsigned long long yesterday, 
		unsigned long long today) 
{
	return n == 0? today : tomorrow(n - 1, yesterday, yesterday + today);
}

unsigned long long h (unsigned short n) {
	return tomorrow (n, 0, 1);
}

int main() {
	cout<< f(93) << endl;
	return 0;
}

#include <iostream>

using namespace std;

unsigned long long tomorrow (

unsigned short n,

unsigned long long yesterday,

unsigned long long today)

{

return n == 0? today : tomorrow(n - 1, yesterday, yesterday + today);

}

unsigned long long h (unsigned short n) {

return tomorrow (n, 0, 1);

}

int main() {

cout<< f(93) << endl;

return 0;

}

Возможно будет легче разобраться если убрать детали

#include <iostream>
using namespace std;
 
unsigned long long f (int i, int p = 0, int c = 1) {
	return i == 0? p : f(i - 1, c, c + p);
}
 
int main() {
	cout<< f(0) << endl;
	cout<< f(1) << endl;
	cout<< f(2) << endl;
	cout<< f(3) << endl;
	cout<< f(4) << endl;
	return 0;
}