Замечания по технике программирования

Рекурсии или итерации

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

Как итерации, так и рекурсии основаны на управляющей структуре: итерации используют структуру повторения, рекурсии используют структуру выбора.

Как итерации, так и рекурсии включают повторение: итерации используют структуру повторения явным образом, рекурсии реализуют повторение посредством повторных вызовов функции.

Как итерации, так и рекурсии включают проверку условия окончания: итерации заканчиваются после нарушения условия продолжения цикла, рекурсии заканчиваются после распознавания базовой задачи.

Как итерации с повторением, управляемым счетчиком, так и рекурсии постепенно приближаются к моменту своего завершения: в итерациях выполняется изменение счетчика до тех пор, пока он не примет значение, при котором перестает выполняться условие продолжения цикла; в рекурсии поддерживается процесс создания упрощенной версии исходной задачи до тех пор, пока не будут достигнута базовая задача.

Как итерации, так и рекурсии могут оказаться бесконечными: бесконечный итеративный цикл возникает, если условие продолжения цикла никогда не становится ложным; бесконечная рекурсия возникает, когда шаг рекурсии не упрощает исходную задачу таким образом, чтобы она сходилась к базовой.

Рекурсия имеет много недостатков. Повторный запуск рекурсивного механизма вызовов функции приводит к росту накладных расходов: к нарастающим затратам процессорного времени или требуемого объема памяти. Каждый рекурсивный вызов приводит к созданию новой копии функции (в самом деле копируются только переменные данной функции); для этого может потребоваться значительная память. Итерации обычно не связаны с функциями, так что в них отсутствуют накладные расходы на повторные вызовы функции и дополнительные затраты памяти. Тогда для чего же применять рекурсию?

Любые задачи, которые можно решить рекурсивно, могут быть решены также и итеративно (нерекурсивно). Обычно рекурсивный подход предпочитают итеративному, если он более естественно отражает задачу и ее результаты, то есть более нагляден и легче отлаживается. Другая причина предпочтения рекурсивного решения состоит в том, что итеративное решение может не быть очевидным.