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