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

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

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

import sys
# Увеличиваем допустимую глубину рекурсии
sys.setrecursionlimit(1500)

def F(n):
    # База: если n < -1000
    if n < -1000:
        return 1

    # Ветка: если n > 1
    if n > 1:
        return -F(n - 1) - F(n - 3)

    # Иначе (для -1000 <= n <= 1)
    return -F(n - 1)

print(F(14))