7.5. Рекурсия

Чаще всего (процедурное) программирование использует итерации, то есть циклы; однако рекурсия — описание объекта или вычисления в терминах са­мого себя — является более простым математическим понятием, а также мощ­ной, но мало используемой техникой программирования. Здесь мы рассмот­рим, как программировать рекурсивные подпрограммы.

Наиболее простой пример рекурсии — функция, вычисляющая фактори­ал. Математически она определяется как:

0! = 1

n! = п х (п - 1)!

Это определение сразу же переводится в программу, которая использует рекурсивную функцию:

int factorial(int n)

if (n == 0) return 1 ;

else return n * factorial(n - 1);

}

Какие свойства необходимы для поддержки рекурсии?

• Компилятор должен выдавать чистый код. Так как при каждом обраще­нии к функции factorial используется одна и та же последовательность машинных команд, код не должен изменять сам себя.

• Должна существовать возможность выделять во время выполнения про­извольное число ячеек памяти для параметров и локальных переменных.

Первое требование выполняется всеми современными компиляторами. Самоизменяющийся код — наследие более старых стилей программирования и используется редко. Обратите внимание, что если программа предназначена для размещения в постоянной памяти (ROM), то она не может изменяться по определению.

Второе требование определяется временем жизни локальных переменных. В примере время жизни формального параметра n — с момента, когда проце­дура вызвана, до ее завершения. Но до завершения процедуры делается еще один вызов, и этот вызов требует, чтобы была выделена память для нового формального параметра. Чтобы вычислять factorial(4), выделяется память для 4, затем 3 и т. д., всего пять ячеек. Нельзя выделить память перед выполнени­ем, потому что ее количество зависит от параметра функции во время выпол­нения. В разделе 7.6 показано, как это требование выделения памяти непо­средственно поддерживается стековой архитектурой.

Большинство программистов обратит внимание, что функцию, вычисляю­щую факториал, можно написать так же легко и намного эффективнее с по­мощью итерации:

int factorial(int n)

{

result = 1;

while (i != 0) {

result = result * i;

i--;

}

return result;

}

Так почему же используют рекурсию? Дело в том, что многие алгоритмы мож­но изящно и надежно написать с помощью рекурсии, в то время как итераци­онное решение трудно запрограммировать и легко сделать ошибки. Приме­ром служат алгоритм быстрой сортировки и алгоритмы обработки дре­вовидных структур данных. Языковые понятия, рассматриваемые в гл. 16 и 17 (функциональное и логическое программирование), опираются исключительно на рекурсию, а не на итерацию. Даже для обычных языков типа С и Ada рекурсию, вероятно, следует использовать более часто, чем это делается, из-за краткости и ясности программ, которые получаются в результате.