Разница между алгоритмами динамического программирования и рекурсивными алгоритмами заключается в подходе к решению задач и в особенностях работы с результатами подзадач. 13

Рекурсивные алгоритмы разбивают большую задачу на более мелкие подзадачи и решают их. 3 При этом каждый новый вызов функции создаёт дополнительные затраты на память и время. 4 Чтобы избежать бесконечной рекурсии, необходимо определить базовый случай, при котором функция должна прекратить вызывать себя и вернуть результат. 4

Алгоритмы динамического программирования делят задачу на кусочки и вычисляют их по очереди, шаг за шагом наращивая решения. 3 При этом каждая подзадача решается только один раз, что сокращает количество вычислений. 35 Для этого решения мелких подзадач сохраняются, например, в таблице. 3

Таким образом, рекурсивные алгоритмы работают «сверху вниз», а алгоритмы динамического программирования — «снизу вверх». 16