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

В задаче дан рекурсивный алгоритм вычисления функции , где для первых трёх значений аргумента заданы конкретные результаты, а для всех используется рекурсивная формула. Реализуем этот алгоритм на Python. Для этого создаём функцию , внутри которой сначала проверяем, относится ли к базовым случаям: при возвращаем , при или — возвращаем . Эти условия позволяют остановить рекурсию и сразу вернуть ответ для небольших значений аргумента. Если , используем формулу , где вычисляем рекурсивно значения для и , а также добавляем квадрат текущего аргумента . Таким образом, на каждом шаге функция делится на более простые подзадачи, пока не достигнет одного из базовых случаев, после чего происходит сворачивание рекурсии с суммированием результатов. После описания алгоритма выполняем вызов , чтобы получить требуемое значение.

def f(n):
    # Если n = 1, базовый случай: возвращаем 0
    if n == 1:
        return 0

    # Если n = 2 или n = 3, второй и третий базовые случаи: возвращаем 1
    elif n == 2 or n == 3:
        return 1

    # Если n > 3, используем рекурсивную формулу
    else:
        # Вычисляем f(n-1) и f(n-2) рекурсивно и прибавляем квадрат n
        return f(n - 1) + n ** 2 + f(n - 2)

# Запускаем алгоритм для n = 25 и выводим результат
print(f(25))