Вызовы рекурсивного программирования против вызовов динамического программирования

Question

Я беру курс по Java 2 и пытаюсь учиться, но я не понимаю эту концепцию:

• В чем разница между вызовами рекурсивного программирования и вызовами динамического программирования?

• Что будет примером для каждого?

Answer 1

Две концепции довольно разные:

• Функция называется рекурсивной, если она сама себя вызывает.

• Динамическое программирование - это метод решения проблем. Это включает в себя сначала решение небольшой подзадачи, а затем расширение решений для решения общей проблемы.

Часто бывает так, что алгоритм динамического программирования может быть выражен рекурсивно.

Answer 2

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

Классическим примером является вычисление n-го числа Фибоначчи:

-Recursive

Fib(n)
  if (n <= 2) return 1
  return Fib(n-1) + Fib(n-2)

-Dynamic

Fib(n)
 previous = 1
 next = 1
 temp = 0
 for i = 2 to n do
   temp = previous
   previous = next
   next = temp + next
 return next

Это псевдокод. Первый повторяет вызовы, а второй основан на предыдущих случаях.

Answer 3

Концептуальные алгоритмы "Разделяй и властвуй" считаются динамическими и рекурсивными, например, сортировка в списках / массивах, где вы разделяете элемент на 2 части и снова вызываете функцию сортировки в каждой части... и так далее

Answer 4

Рекурсивный код - это код, который вызывает сам себя, динамический код - это код, который программирует, а затем вызывает себя.

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