Fibo

// Рекурсия. <<Разделяй и властвуй>>
// F_n = F_(n-1) +F_(n-2), F_0 = 0, F_1 = 1
#include <iostream>

int fibo1(int n) {
    if(n == 0) return 0;
    if(n == 1) return 1;
    return fibo1(n-1) + fibo1(n-2);   //Простая версия с понятной реализацией, но проблемой с повторным вычислением
}

int fibo(int n) {
    const int MAXN = 1000; //Выбрали размер максимальный
    static int c[MAXN];     //Создали массив куда будем запоминать вычисления
    if(n == 0) return 0;
    if(n == 1) return 1;
    if(c[n]>0) return c[n];    //Если уже записали то просто это и вернем
    return c[n] = fibo(n-1) + fibo(n-2);   //Иначе вычислим и запишем


}


int main()
{
    std::cout <<fibo(6);
    return 0;
}