Lesson_2_2.py

"""
Задание 2.

Последовательностью Фибоначчи называется
последовательность чисел a0
, a1
, ..., an
, ..., где
a0 = 0, a1 = 1,
ak = ak-1 + ak-2 (k > 1).
Требуется найти N-е число Фибоначчи
Input: 7
Output: 21
"""

'''
# 0, 1, 1, 2, 3, 5, 8, 13, 21
a = 7
fibo_p, fibo_n = 0, 1
for _ in range(0, a):
    fibo_p, fibo_n = fibo_n, fibo_p + fibo_n
print(f'{a}-e число = {fibo_n}')

'''

def fib(n):
    """
    Рекурсивно вычисляет n-е число Фибоначчи
    для a0 = 0, a1 = 1, ak = a_{k-1} + a_{k-2}.
    """
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

if __name__ == "__main__":
    # Считываем N
    n = int(input("Введите N: "))
    # По примеру цикла из предыдущей задачи
    # выводили fib(n+1), чтобы для N=7 получить 21
    result = fib(n + 1)
    print(result)