Количество рекурсий

Question

def recursion(n):
    return 1 if n == 1 else 1 + recursion(n - recursion(recursion(n - 1)))
 
print(recursion(int(input())))

Я написал код но он слишком долгий, можно как нибудь его ускорить?

Answer 1

Если вы переиспользуете функцию, то можно кэшировать результат с помощью стандартной библиотеки python

from functools import lru_cache

@lru_cache(maxsize=None)
def recursion(n):
    return 1 if n == 1 else 1 + recursion(n - recursion(recursion(n - 1)))

Answer 2

можно попробовать самому реализовать lru_cache

def lru_cache(func):
    dict_ = {}
    def wrapper(n):
        if n not in dict_:
            dict_[n] = func(n)
        return dict_[n]
    return wrapper

@lru_cache
def recursion(n):
    return 1 if n == 1 else 1 + recursion(n - recursion(recursion(n - 1)))

БЛОГ НА HUSL

Количество рекурсий

Ответы (2 шт):