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

Решение программой:

Функция определяется рекурсивно по 2 правилам: при возвращаем 2 ** n, при вычисляем как . Для нахождения напрямую вызовем функцию.

# Базовые случаи: для n < 4 возвращается 2 ** n — они задают начальные значения и останавливают рекурсию
# Рекурсивное правило: f(n) определяется по формуле: 2 * f(n - 1) + f(n // 2)
def f (n):  # Определение функции, реализующей алгоритм из условия
    if n < 4:  # Базовый случай — возвращаем значение без рекурсии
        return 2 ** n  # Возвращаем базовое значение
    if n % 2 == 0:  # Рекурсивный случай — возвращаем выражение с рекурсивным вызовом
        return 2 * f(n - 1) + f(n // 2)  # Возвращаем значение рекурсивного выражения
    return f(n - 2) + 2 * n + 1 + f(n // 3)  # Возвращаем значение рекурсивного выражения

print(f(128))  # Выводим результат на экран