Рекурсивный вызов подпрограмм
Применение стека для хранения записей активации позволяет реализовывать не только последовательный вызов подпрограмм, но и рекурсивный вызов.
Рекурсивным вызовом подпрограммы называется вызов подпрограммы из самой себя. При n вызовах подпрограммы A в стек будет последовательно добавлено n записей активации этой подпрограммы. Последний вызов подпрограммы A будет завершен первым, и его запись активации будет первой удалена из стека.
Примером использования рекурсии может служить программа вычисления факториала n! =(n*(n-1)!), 0!=1.
Пример подпрограммы на языке С:
int factoria(int n) { if (n) return n* factoria(n-1); else return 1; }
В некоторых случаях без применения рекурсии задачу решить практически невозможно. Хорошо известен пример программирования алгоритма ханойских башен. Условия задачи состоят в следующем: есть три башни, первая башня состоит из колец, диаметр которых увеличивается сверху вниз. Задача заключается в программировании алгоритма, обеспечивающего перемещение колец с первой башни на вторую по одному с возможным использованием вспомогательной третьей башни таким образом, чтобы все кольца оказались на второй башне и их диаметр увеличивается сверху вниз. Алгоритм решения этой задачи посредством рекурсии состоит в предположении, что эта задача решена для n-1 кольца. Тогда, если при n=1 решение задачи очевидно, то есть решение и для n колец.
Пример подпрограммы на языке С++, реализующей алгоритм ханойских башен:
#include "stdafx.h" #include <iostream> void tower_3(int n, int m, int k); int main(int argc, _TCHAR* argv[]) { tower_3 (3,1,3); return 0; }
void tower_3(int n, int m, int k){ /* n - число перемещаемых колец m - башня, с которой выполняется перемещение k - башня, на которую выполняется перемещение */
if (n==1) { //Последнее очевидное перемещение return ;}
tower_3(n-1,m,6-m-k); /* 6-m-k определяет номер вспомогательной башни, m - номер башни, с которой выполняется перемещение */
std::cout<<" from "<< m << " to "<< k << " n= "<<n-1<<std::endl; tower_3(n-1,6-m-k,k); /* 6-m-k- номер башни, с которой выполняется перемещение */ }
На рисунке 4.2 приведен пример выполнения алгоритма ханойских башен для трех колец (n указывает количество перекладываемых колец).
Рис. 4.2. Результат рекурсивного вызова процедуры.
Одним из первых языков программирования, допускавших рекурсию, являлся ALGOL 60. Раньше принципы реализации записей активации трансляторами языка FORTRAN не позволяли применять рекурсию, но последняя версия компилятора языка FORTRAN 90 это допускает.
Подпрограммы A и B называются взаимно рекурсивными, если подпрограмма A вызывает B, а подпрограмма B вызывает A.
Языки программирования, для которых традиционно используются однопроходные компиляторы, для реализации взаимной рекурсии должны вводить предварительное определение подпрограммы. Это объясняется тем, что при взаимно рекурсивном вызове подпрограмм A и B, в момент вызова B из A подпрограмма B должна быть уже определена, а в момент вызова A из B подпрограмма A должна быть определена. Такой механизм используется в языках Pascal и Ada.
Язык Pascal не требует указания сигнатуры функции или процедуры в том случае, если ее определение расположено в коде программы до ее вызова. В противном случае используется предварительное определение, указываемое ключевым словом forward.
На рисунке 4.3 приведен код модуля на языке Pascal (созданного в среде Delphi), иллюстрирующий предварительное объявление функции A.
Рис. 4.3. Предварительное объявление функции.
Следует отметить, что компиляция программ, удовлетворяющих стандарту языка программирования, различными трансляторами может создавать различный выполнимый код. При этом очень часто компиляторы несколько "расширяют" диапазон возможностей, предоставляемых стандартом языка программирования. Такая ситуация будет приводить к ограничению использования "расширенного" синтаксиса программы с другими компиляторами.
