Все методы разделения и завоевания используют рекурсивные функции или не обязательно?

Question

Выполняют ли все алгоритмы, использующие подход «разделение и захват», рекурсивные функции или необязательно?

Answer 1

Двоичный поиск - это применение парадигмы D &. (Как показано ниже: разделение на две половины и продолжение в половине, которая может содержать ключ.)

Он может быть реализован как рекурсивно, так и не рекурсивно.

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

---

В самом широком смысле, D & C является отцом всех алгоритмов при заявленных как «разбить задачу на подзадачи проще одного и того же рода». Это определение также охватывает итеративные решения, часто реализуемые без рекурсии.