На этом шаге мы наметим план дальнейшего изложения.
Такие преимущества рекурсии над итерацией, как ясность кода или неявное управление стеком, проявляются главным образом при использовании множественной рекурсии. Основанные на этом типе рекурсии методы вызывают себя несколько раз, по крайней мере, в одном рекурсивном условии. Поэтому такие алгоритмы решают несколько простых подзадач, а затем должны объединить, расширить и/ или изменить их результаты для получения решения исходной задачи.
Начиная с этого шага, мы начнем рассматриватьважный класс алгоритмов с множественной рекурсией для задач, декомпозиция которых основана на делении их размера на некоторую константу. Говорят, что такие алгоритмы следуют принципу "разделяй и властвуй" - одной из самых важных парадигм разработки алгоритмов. Его можно рассматривать как общую стратегию решения задач, состоящую в разбиении задачи на несколько подобных себе подзадач, размер которых составляет некоторую часть размера исходной задачи. Поэтому такой подход имеет прямое отношение к рекурсии (итерационные алгоритмы тоже могут следовать этой стратегии), поскольку он опирается на рекурсивную декомпозицию задачи (см. рисунок 1 шага 4). Функция в примере 1.2 и третий метод в примере 1.5 - примеры такого подхода к разработке алгоритма.
В некоторых источниках термин "разделяй и властвуй" применяется и к тем алгоритмам, декомпозиция которых сводится к единственной подзадаче в половину размера исходной (с единственным вызовом метода). Однако многие авторы полагают, что этот термин должен применяться только тогда, когда решение предполагает разбиение задачи на две и более подзадач. Здесь принимается именно это последнее соглашение. Таким образом, методы, делящие размер задачи пополам, но вызывающие себя лишь раз, уже были приведены ранее. В следующих шагах описаны классические рекурсивные алгоритмы, следующие принципу "разделяй и властвуй".
На следующем шаге мы рассмотрим задачу определения отсортированности списка.
