Первое требование выполняется всеми современными
Первое требование выполняется всеми современными компиляторами. Самоизменяющийся код — наследие более старых стилей программирования и используется редко. Обратите внимание, что если программа предназначена для размещения в постоянной памяти (ROM), то она не может изменяться по определению.
Второе требование определяется временем жизни локальных переменных. В примере время жизни формального параметра n — с момента, когда процедура вызвана, до ее завершения. Но до завершения процедуры делается еще один вызов, и этот вызов требует, чтобы была выделена память для нового формального параметра. Чтобы вычислять factorial(4), выделяется память для 4, затем 3 и т. д., всего пять ячеек. Нельзя выделить память перед выполнением, потому что ее количество зависит от параметра функции во время выполнения. В разделе 7.6 показано, как это требование выделения памяти непосредственно поддерживается стековой архитектурой.
Большинство программистов обратит внимание, что функцию, вычисляющую факториал, можно написать так же легко и намного эффективнее с помощью итерации:
int factorial(int n)
{
C |
result = 1;
while (i != 0) {
result = result * i;
i--;
}
return result;
}
Так почему же используют рекурсию? Дело в том, что многие алгоритмы можно изящно и надежно написать с помощью рекурсии, в то время как итерационное решение трудно запрограммировать и легко сделать ошибки. Примером служат алгоритм быстрой сортировки и алгоритмы обработки древовидных структур данных. Языковые понятия, рассматриваемые в гл. 16 и 17 (функциональное и логическое программирование), опираются исключительно на рекурсию, а не на итерацию. Даже для обычных языков типа С и Ada рекурсию, вероятно, следует использовать более часто, чем это делается, из-за краткости и ясности программ, которые получаются в результате.
