Var a, X : Vector; b : Integer; I : Integer;

{Procedure WriteSolution печатает решение X[1..n]}

{Procedure Solution}

Begin {раздел операторов основной программы}

{Ввод массива a[1..n] и св. члена b}

Solution(n, b)

End.

Преимущества и недостатки рекурсивных алгоритмов

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

Так, задачи примеров 2, 3, 6, 7 допускают более эффективные и достаточно простые итеративные решения. В примере 6 это продемон­стри­ровано особенно наглядно.

В примерах 2, 3, 7 рекурсия моделирует простой цикл, тратя время на вычисления, связанные с управлением рекурсивными вызо­вами и память на динами­ческое хранение данных. Сложнее реали­зовать итеративную версию алгоритма примера 4.

Несомненным достоинством алгоритмов из примеров 3, 5, 8 является их простота и обоснованность. При програм­ми­ро­ва­нии мы по существу одновременно обосновывали прави­ль­ность алгоритма. В примерах 5, 8, 9 рассматриваются комбинаторные задачи, решение кото­рых не сводится к простому применению цикла, а требует перебора вариантов, естест­венным образом управляемого рекурсивно. Итеративные версии решений этих задач сложнее по управлению. Можно сказать, что основная вычислительная сложность комбинаторной задачи заключена не в реализации алгоритма ее решения, а в самом методе решения.

Позже мы увидим, как рекурсия в сочетании с другими метода­ми используется для построения эффективных алгоритмов.

22