16.01 Одна функция

Рекурсивное решение

В задаче задан рекурсивный алгоритм, при котором функция в процессе вычислений вызывает сама себя с другими аргументами. Для реализации создаём пользовательскую функцию в Python с помощью . Внутри функции используем условный оператор , чтобы задать ветвление: , , , рекуррентная формула для : . Реализуем рекурсивно по определению и вычислим .

def f(n):
    # База 1: F(1) = 0
    if n == 1:
        return 0
    # База 2: F(2) = 1, F(3) = 1
    if n in [2, 3]:
        return 1
    else:
        # Рекуррентная формула: F(n) = F(n-1) + F(n-2)
        return f(n - 1) + f(n - 2)

print(f(11))