Задача

Необходимо найти n-ый член последовательности , если: $F_{0}= 0$, $F_{1}= 1$, $F_{n}= F_{n-1}+ F_{n-2}$, где $n\geq2$, $n \in Z$

По рекуррентной формуле $F_{n}= F_{n-1}+ F_{n-2}$ происходит обращение к предыдущим членам последовательности

Начальные значения последовательности: $F_{0}= 0$, $F_{1}= 1$

Все промежуточные значения ищутся многократно. Сложность решения $O(2^n)$

Псевдокод:

функция фибоначчи(n)
    если n = 0, то
        вернуть 0
    eсли n = 1 или n = 2, то
        вернуть 1
    вернуть фибоначчи(i - 1) + фибоначчи(i - 2)    

#python

def fib_recursion(n):
    if n < 0:
        return -1
    if n == 0:
        return 0
    if n == 1 or n == 2:
        return 1
    return fib_recursion(n - 1) + fib_recursion(n - 2)

//C++
//sport version

int fib_recurs(int n){
    if(n < 0){
        return -1;
    }
    if(n == 0){
        return 0;
    }
    if(n == 1 or n == 2){
        return 1;
    }
    return fib_recurs(n - 1) + fib_recurs(n - 2);
}

//C++
//production version

template<typename ValueType>
ValueType fibonacci_recursion(ValueType n){
    if(n < 0){
        return -1;
    }
    if(n == 0){
        return 0;
    }
    if(n == 1 or n == 2){
        return 1;
    }
    return fibonacci_recursion(n - 1) + fibonacci_recursion(n - 2);
}