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

Решение:

Здесь рекурсия опирается только на меньшие аргументы, поэтому значения удобно считать подряд, от $n = 0$ до $n = 39$, складывая их в массив. База: $F(0) = F(1) = F(2) = 1$. Для нечётного $n \gt 2$ берём разность двух предыдущих значений, а для чётного — сумму всех значений от $F(1)$ до $F(n-1)$, то есть накопленную сумму уже посчитанной части массива.

Первые значения: $F(3) = F(2) - F(1) = 0$, $F(4) = F(1) + F(2) + F(3) = 2$, $F(5) = F(4) - F(3) = 2$, $F(6) = 1 + 1 + 0 + 2 + 2 = 6$, $F(7) = 6 - 2 = 4$, $F(8) = 16$. Видно, что напрямую «в лоб» рекурсию писать не стоит: чётная ветвь заново пересчитывает всю историю, поэтому либо заполняем массив снизу вверх, либо кэшируем результаты.

Продолжая таблицу до $n = 39$, получаем $F(39) = 41518080$.

F = [0] * 40
F[0] = F[1] = F[2] = 1
for n in range(3, 40):
    if n % 2 == 1:
        F[n] = F[n - 1] - F[n - 2]
    else:
        F[n] = sum(F[1:n])
print(F[39])   # 41518080

Ответ: 41518080