SBU021RecursionBasic

#include <iostream>

//n!= 1 * 2 * 3 * 4 ... n-1 * n
//
//n! = n * (n - 1)! = n * (n -1) * ( n - 1 - 1)! = n * (n - 1) * ( n - 1 -1 ) * ( n -1 -1 -1 )!
//0! = 1;

/*
3! = 3 * (3-1)!
(3-1)! = 2! = 2 * (2-1)!
(2-1)! = 1! = 1 * (1-1)!
(1-1)! = 0! = 1

1! = 1;
2! = 2;
3! = 6;


*/
/*
fakt(3) -> 3 * fakt(2) -> 2 * fakt(1) -> 1 * fakt(0)
fakt(0) => 1 * 1 -> fakt(1) => 1 * 2 -> fakt(2) => 2 -> 2*3 -> fakt(3) => 6
*/

//0! = 1;
//n! = n * (n - 1)!


int fakt(int n)
{
    if (n == 0) return 1;
    return n * fakt(n - 1);
}

int fib(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
}

int fib1(int n)
{
    int res{ 0 };
    int arr[2]{ 0,1 };
    if (n == 0) return 0;
    if (n == 1) return 1;
    for (int i{ 2 }; i <= n; ++i)
    {
        res = arr[0] + arr[1];
        arr[0] = arr[1];
        arr[1] = res;
    }
    return res;
};

int main()
{
    int maxNum{ 47 };
    //std::cout << n <<"!=" << fakt(n) << '\n';
    //std::cout << "FIB(" << n << ")=" << fib(n) << '\n';
    //std::cout << "FIB1(" << n << ")=" << fib1(n) << '\n';

    //for(int i{0}; i<maxNum; ++i)
    //{
    //  std::cout << fib(i) << ' ';
    //}

    std::cout << '\n';

    for (int i{ 0 }; i < maxNum; ++i)
    {
        std::cout << fib1(i) << ' ';
    }
}