Рекурсия — это метод программирования, при котором функция многократно вызывает саму себя до тех пор, пока не будет выполнено условие завершения. Некоторые из примеров, где используется рекурсия: вычисление рядов Фибоначчи, факториал и т. Д. Но проблема с ними заключается в том, что в дереве рекурсии может быть вероятность того, что подзадача, которая уже решена, решается снова, что увеличивает накладные расходы.
Запоминание — это метод записи промежуточных результатов, с помощью которого можно избежать повторных вычислений и ускорить выполнение программ. Его можно использовать для оптимизации программ, использующих рекурсию. В Python запоминание может быть выполнено с помощью декораторов функций.
Давайте возьмем пример вычисления факториала числа. Приведенная ниже простая программа использует рекурсию для решения проблемы:
# Simple recursive program to find factorial
def facto(num):
if num == 1:
return 1
else:
return num * facto(num-1)
print(facto(5))
Вышеуказанная программа может быть оптимизирована путем запоминания с помощью декораторов.
# Factorial program with memoization using
# decorators.
# A decorator function for function 'f' passed
# as parameter
def memoize_factorial(f):
memory = {}
# This inner function has access to memory
# and 'f'
def inner(num):
if num not in memory:
memory[num] = f(num)
return memory[num]
return inner
@memoize_factorial
def facto(num):
if num == 1:
return 1
else:
return num * facto(num-1)
print(facto(5))
Пояснение:
1. Определена функция, называемая memoize_factorial. Его основная цель-сохранить промежуточные результаты в переменной, называемой памятью.
2. Вторая функция, называемая факто, — это функция вычисления факториала. Он был аннотирован декоратором(функция memoize_factorial). В результате концепции замыканий у пользователя есть доступ к переменной памяти. Аннотация эквивалентна написанию:
facto = memoize_factorial(facto)3. При вызове facto(5) рекурсивные операции выполняются в дополнение к хранению промежуточных результатов. Каждый раз, когда необходимо выполнить расчет, проверяется, доступен ли результат в память. Если да, то он используется, в противном случае значение вычисляется и сохраняется в память.
4. Мы можем проверить тот факт, что запоминание действительно работает, пожалуйста, смотрите вывод этот программа.
