На этом шаге мы сравним итерацию и рекурсию.
Вычислительная мощь компьютеров заключается главным образом в их способности выполнять задачи многократно - итерационно или рекурсивно. Первые для многократного повторения действий используют такие конструкции, как циклы while или for, тогда как рекурсивные функции раз за разом вызывают самих себя, при каждом вызове вплоть до достижения начального условия решая одну и ту же задачу. Итерация и рекурсия эквивалентны в том смысле, что они решают одни и те же виды задач. Всякая итеративная программа может быть преобразована в рекурсивную, и наоборот. Выбор может зависеть от нескольких факторов, таких как вычислительная задача, эффективность, язык или парадигма программирования. Например, итерация предпочтительна в императивных языках, тогда как рекурсия широко используется в функциональном программировании, которое следует декларативной парадигме программирования.
Уже приведённые на предыдущих шагах примеры могут быть легко закодированы с помощью циклов. Поэтому выгода от применения рекурсии ещё не вполне ясна. На практике основное преимущество использования рекурсивных алгоритмов вместо итерационных заключается в том, что для многих вычислительных задач рекурсивный алгоритм гораздо проще проектировать и понимать. Рекурсивный алгоритм больше похож на логический подход к решению задач. Следовательно, он должен быть более понятным, изящным и коротким.
Кроме того, рекурсивные алгоритмы неявно используют для хранения информации программный стек, операции с которым (скажем, втолкнуть и вытолкнуть) прозрачны для программиста. Поэтому они предоставляют ясные альтернативы итерационным алгоритмам, где ответственность за явное управление стековой (или подобной ей) структурой данных ложится на программиста. Например, если условие задачи или структура данных предполагает дерево, рекурсивные алгоритмы будут гораздо проще и понятнее итерационных, поскольку для последних нужно реализовывать поиски в ширину или в глубину с использованием очередей и стеков соответственно.
С другой стороны, в самом общем случае рекурсивные алгоритмы не столь эффективны, как итерационные, и используют больше памяти. Эти недостатки связаны с использованием программного стека. Вообще, каждый вызов функции, рекурсивный он или нет, выделяет память в программном стеке и хранит в нём информацию, требующую дополнительных вычислительных затрат. Таким образом, рекурсивная программа может быть не только медленнее итерационной - большое количество вызовов при выполнении программы может привести к переполнению стека. Более того, некоторые рекурсивные определения сами по себе могут быть довольно медленными. Например, коды для чисел Фибоначчи в примерах 1.3 и 1.4 требуют экспоненциального времени выполнения, тогда как числа Фибоначчи могут быть вычислены (гораздо быстрее) за логарифмическое время. Помимо этого, рекурсивные алгоритмы сложнее для отладки (то есть для пошагового анализа программы с целью поиска и локализации ошибок), особенно если функции вызывают себя многократно, как в примерах 1.3 и 1.4.
Наконец, если в некоторых функциональных языках программирования циклы вообще не допускаются, то многие иные языки поддерживают как итерацию, так и рекурсию. Поэтому в них можно объединять оба этих стиля программирования так, чтобы создавать алгоритмы не только мощные, но и ясные для понимания (например, перебор с возвратами). В примере 1.4 реализована рекурсивная функция с применением цикла.
На следующем шаге мы рассмотрим типы рекурсии.
