Бифуркационные рекурсивные вычисления с избыточными вычислениями

def T(n):
  if n <= 0:
    return 1
  else:
    return T(n-1) + (n-1) * T(n-2)
    
print T(4)

Мне нужен эффективный способ распечатать вывод функции T(n) генерируется с использованием приведенного выше рекуррентного отношения Есть ли способ сделать приведенный выше код более эффективным?

Пример вывода:

10

Если вы не можете использовать functools.cache или же functools.lru_cache и если вы не понимаете или не хотите использовать декоратор, как показано в другом ответе, здесь нетехнологичный подход к мемоизация. Обратите внимание, что functools подход проще, надежнее и т.д. Но если вы не беспокоитесь обо всем этом и просто хотите простой код, который радикально быстрее, чем ваш текущий подход, это сработает.

def T(n):
    if n not in T.cache:
        if n <= 0:
            T.cache[n] = 1
        else:
            T.cache[n] = T(n-1) + (n-1) * T(n-2)
    return T.cache[n]

# Initialize the cache.
T.cache = {}

Еще один вариант — вообще не использовать рекурсию, а вместо этого вычислять последовательность, пока мы не получим желаемый член. Это не только позволяет избежать экспоненциальной сложности исходного алгоритма; это также позволяет избежать, по крайней мере, линейной (с точки зрения подсчета значений) сложности памяти при мемоизации. (Рекурсия / мемоизация также могут вызывать проблемы, связанные с реализацией, такие как ошибки глубины рекурсии или ошибки памяти, которые не связаны с приведенным ниже кодом.)

def T(n):
    if n<=0: return 1
    # Set a, b to T(-1), T(0)
    a, b = 1, 1
    for i in range(n):
        # Change a, b from T(i-1), T(i) to T(i), T(i+1)
        a, b = b, b+i*a
    # i=n-1 set b to T(n)
    return b

Вы должны использовать if "__name__" == __main__: сторожить.

Из Python 3.2 вы можете использовать functools.lru_cache а из Python 3.9 вы можете использовать functools.cache запоминать вызовы функций, только вызывать T $ O (п) $ раз. Это причудливое название для кеширования ввода и вывода функции. Это работает путем обертывания функции. Каждый раз, когда вызывается декорированная функция, мы сравниваем аргументы с ключами в кеше:

• если есть совпадение, мы возвращаем значение, и
• если совпадений нет, мы вызываем функцию, чтобы получить возвращаемое значение. Сохраните возвращаемое значение в кеше и верните возвращенное значение вызывающей стороне.

Поскольку вы используете Python 2, мы можем сделать эту функцию сами. Мы можем использовать замыкание для создания функции-декоратора для хранения кеша.

def cache(fn):
    def inner(*args):
        try:
            return CACHE[args]
        except KeyError:
            pass
        CACHE[args] = value = fn(*args)
        return value
    CACHE = {}
    return inner

@cache
def T(n):
  if n <= 0:
    return 1
  else:
    return T(n-1) + (n-1) * T(n-2)