Рекурсия, Последний шаг, Разрыв цепочки рекурсии

А причём здесь рекурсия? Задача решается не рекурсией, а динамическим программированием - с вычислительной сложностью O(n).

# вычисление кол-ва способов получения числа i
# по ранее вычисленному кол-ву способов получения чисел от 0 до i - 1
def step(t, i):
~~if i % 2: t[i] = [t[i - 1][1] + t[i - 2][0], t[i - 2][0]]
~~else: t[i] = [t[i - 1][1] + t[i - 2][0] + t[i // 2][0], t[i - 2][0] + t[i // 2][0]]

# собственно получение результата
t = [[0, 0] for _ in range(80)] # инициализируем массив t
t[3] = [1, 1] # начинаем с числа 3
for i in range(4, 12): step(t, i) # кол-во способов получения чисел от 4 до 11
for i in range(0, 11): t[i] = [0, 0] # удаляем способы, не включающие 11
for i in range(12, 23): step(t, i) # кол-во способов получения чисел от 12 до 22
# кол-во способов получения числа 23 остаётся равным 0
for i in range(24, 80): step(t, i) # кол-во способов получения чисел от 24 до 79
print(t[79][0]) # итого


t[i][0] - кол-во способов получения числа i в которых последней операцией может быть "прибавить 1"
t[i][1] - кол-во способов получения числа i в которых последней операцией НЕ может быть "прибавить 1"