Задание №16 — Рекурсия

Решение:

Число 17 нечётное, поэтому работает третье правило $F(n) = 1 + 3 \cdot F(n-2)$. Оно уменьшает аргумент сразу на 2, то есть из нечётного числа мы снова попадаем в нечётное и спускаемся до $F(1) = 1$. Правило для чётных $n$ в этой цепочке не используется вообще.

$F(1) = 1$, $F(3) = 1 + 3 \cdot 1 = 4$, $F(5) = 1 + 3 \cdot 4 = 13$, $F(7) = 1 + 3 \cdot 13 = 40$, $F(9) = 121$, $F(11) = 364$, $F(13) = 1093$, $F(15) = 3280$, $F(17) = 1 + 3 \cdot 3280 = 9841$.

Тот же результат виден и по формуле: раскрывая скобки, получаем сумму геометрической прогрессии $$F(17) = 3^{8} + 3^{7} + \dots + 3 + 1 = \frac{3^{9} - 1}{2} = \frac{19683 - 1}{2} = 9841.$$

from functools import lru_cache

@lru_cache(None)
def F(n):
    if n == 1:
        return 1
    if n % 2 == 0:
        return n + 2 * F(n - 1)
    return 1 + 3 * F(n - 2)

print(F(17))   # 9841

Ответ: 9841