Рекурсия

Предположим, что имеется ситуация:

main() /* вызывающая функция */ { ... f() ...} f() /* рекурсивная функция */ { ... f() ...} Здесь в функции main вызывается рекурсивная функция f. Требуется заменить описание функции f и ее вызова на эквивалентный фрагмент программы, т.е. удалить функцию f.

Пусть рекурсивная функция f имеет параметры Р1,Р2,...,Рs, внутренние переменные V1,V2,...,Vt и в функциях main и f имеется k обращений к функции f. Для удаления такой функции требуются следующие дополнительные объекты:

- переменные AR1,AR2,...,ARs, содержащие значения фактических параметров при вызове функции f (типы переменных должны соответствовать типам параметров Р1,Р2,...,Рs);

- переменная rz для вычисляемого функцией f результата (тип переменных совпадает с типом возвращаемого значения функции f);

- стек, содержащий в себе все параметры и все внутренние переменные функции f, а также переменную lr типа int, для хранения точки возврата, и переменную pst типа указатель, для хранения адреса предыдущего элемента стека;

- указатель dl для хранения адреса вершин стека;

- промежуточный указатель u для операций над стеком;

- k новых меток L1,...,Lk для обозначенных точек возврата;

- метка jf, используемая для обхода модифицированного тела функции f;

- промежуточная переменная l типа int для передачи номера точки возврата.

Чтобы получить эквивалентную нерекурсивную программу без функции f, необходимо выполнить следующие действия:

1. Убрать объявление функции f в функцию main;

2. Добавить в функции main объявления переменных AR1,AR2,...,ARs,RZ, объявления стека ST и указателей dl и u:

typedef struct st { P1;P2;...;Ps;V1;V2;...;Vt; int lr; struct st *pst } ST; ST *dl=NULL, *u; 3. Модифицировать тело функции f во фрагмент программы. Для этого следует:

а) удалить заголовок функции f;

б) объявления параметров и внутренних переменных и заменить фрагментом:

goto jf; f: a=malloc(sizeof(ST)); a->P1=AR1; a->P2=AR2; ... ;a->Ps=ARs; a->lr=l; a->pst=dl; dl=a; в) в конце функции f поставить метку JF, а все обращения к формальным аргументам заменить обращением, к соответствующим элементам стека;

г) вместо каждого оператора return(y) в функции f записать фрагмент:

RZ=y; l=dl->lr; a=dl; dl=a->pst; free(a); switch(l) { case 1: goto L1; case 2: goto L2; ... case k: goto Lk; } 4. Каждый i-тый вызов функции f (как в вызывающей функции, так и в теле функции f) вида V=f(A1,A2,...,As) заменить фрагментом программы:

AR1=A1; AR2=A2; ... ; ARs=As; l=i; goto f; Li: V=RZ; где l=i обозначает l=1 при первом обращении к функции f, l=2 при втором обращении и т.д. Нумерация обращений может быть выполнена в произвольном порядке и требуется для возвращения в точку вызова с помощью операторов switch и goto Li; (где Li есть L1 при первой замене, Li есть L2 при второй замене и т.д.)

5. Вставить модифицированное тело функции f в конце функции main.

Для иллюстрации изложенного рассмотрим несколько вариантов реализации программы вычисляющей функцию Аккермана, которая определяется так:

+ X+1, если N=0 | X, если N=1, Y=0, | 0, если N=2, Y=0, A(N,X,Y)= | 1, если N=3, Y=0, | 2, если N=>4, Y=0, + A(N-1,A(N,X,Y-1),X), если N#0, Y#0; где N,X,Y - целые неотрицательные числа.