Трибоначчи рекурсивно

Рекурсивное вычисление n-го числа ряда Фибоначчи

1. Если n = 1 или n = 2, вернуть в вызывающую ветку единицу, так как первый и второй элементы ряда Фибоначчи равны единице.
2. Во всех остальных случаях вызвать эту же функцию с аргументами n - 1 и n - 2. Результат двух вызовов сложить и вернуть в вызывающую ветку программы.

def fibonacci(n):
    if n in (1, 2):
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))

Допустим, n = 4. Тогда произойдет рекурсивный вызов fibonacci(3) и fibonacci(2). Второй вернет единицу, а первый приведет к еще двум вызовам функции: fibonacci(2) и fibonacci(1). Оба вызова вернут единицу, в сумме будет два. Таким образом, вызов fibonacci(3) возвращает число 2, которое суммируется с числом 1 от вызова fibonacci(2). Результат 3 возвращается в основную ветку программы. Четвертый элемент ряда Фибоначчи равен трем: 1 1 2 3.

def tribonacci(n):
    if n in (1, 2):
        return 0
    if n in (3,):
        return 1
    return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)

В разы быстрее варианта @Akina, 70ый меньше чем за секунду

def tribonacci(n, n2=None, n3=None):
    if n in (1, 2):
        return 0
    if n in (3,):
        return 1

    n3 = n3 or tribonacci(n - 3)    
    n2 = n2 or tribonacci(n - 2, n3)

    return tribonacci(n - 1, n2, n3) + n2 + n3

tribonacci(70)

Но на кеше всеравно быстрее

import functools

@functools.lru_cache(maxsize=4)
def tribonacci(n):
    if n in (1, 2):
        return 0
    if n in (3,):
        return 1
    return tribonacci(n - 1) + tribonacci(n - 2) + tribonacci(n - 3)

tribonacci(100)

  n=int(input())
  a=0
  b=0
  c=1
  while n>0:
    n-=1
    h=a+b+c
    a=b
    b=c
    c=h
  print(c-a-b)  
  print(a)
  print(b)
  print(c)