Это такой подход в решении в котором программист декомпозирует задачу на более простые подзадачи. Как правило разбивая на мелкие задачи, программист уменьшает сложность, и снижает количество вычислений. Хороший пример рекурсивное решение последовательности Фибоначчи когда программа вызывает экспоненциально тот же стек вызовов, каждый раз вызывая уже вычисленное значение в каждом новом вызове. Конечно такой подход не совсем оптимален с точки зрения вычислительных ресурсов.
def recursive_fibonacci(n):
if n <=2:
return 1
else:
return recursive_fibonacci(n - 1) + recursive_fibonacci(n - 2)
решение с рекурсисей
Мемоизация - подход в динамическом программировании когда имеет смысл сохранения вычисленных подзадач. Какой смысл делать те же самые вычисления много раз? Не лучше ли их записать, а в нужный момент просто извлечь готовое вычисленное решение. Конечно да !
def memoized_fibonacci(n):
memo = {}
if n in memo:
return memo[n]
if n <= 2 :
return 1
else:
result = memoized_fibonacci(n - 1) + memoized_fibonacci(n - 2)
memo[n] = resulter
return resulter
решение с мемоизацией
Сверху вниз, и снизу вверх.
продолжение ....