Последовательность вызовов процедуры tn при m=3 иллюстрируется древовидной структурой на рис.33. Каждый раз при вызове процедуры tn под параметры n, i, j, w выделяется память и запоминается место возврата. При возврате из процедуры tn память, выделенная под параметры n, i, j, w, освобождается и становится доступной память, выделенная под параметры n, i, j, w предыдущим вызовом, а управление передается в место возврата.

Рис.33. Последовательность вызовов процедуры tn.

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

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

Здесь в функции 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:

3. Модифицировать тело функции f во фрагмент программы. Для этого следует:

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

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

в) в конце функции f поставить метку JF, а все обращения к формальным аргументам заменить обращением, к соответствующим элементам стека;

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

4. Каждый i-тый вызов функции f (как в вызывающей функции, так и в теле функции f) вида V=f(A1,A2,...,As) заменить фрагментом программы :

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

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

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

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

main () /* вызывающая */ { int x,y,n,t; /* функция */ int ackr(int, int, int); scanf("%d %d %d",&n,&x,&y); t=ackr(n,x,y); printf("%d",t); } int smacc( int n,int x ) /* вспомогательная */ { switch (n) /* функция */ { case 0: return(x+1); case 1: return (x); case 2: return (0); case 3: return (1); default: return (2); } } int ackr( int n, int x, int y) /* рекурсивная */ { int z; /* функция */ int smacc( int,int); if(n==0 || y==0) z=smacc(n,x); else { z=ackr(n,x,y-1); /* рекурсивные */ z=ackr(n-1,z,x); } /* вызовы ackr(...) */ return z; }

Модифицируя функции main и ackr в соответствии с изложенным методом получим следующую программу:

/* Эквивалентная нерекурсивная программа */ /* для вычисления функции Аккермана */ #include #include int main() { typedef struct st { int i,j,k,z,lr; struct st *pst; } ST; ST *u, *dl=NULL; int l,x,y,n; int smacc(int,int); int an,ax,ay,rz,t; scanf("%i %i %i",&n,&x,&y); an=n;ax=x;ay=y;l=1; /* - замена вызова - */ goto ackr; /* t=ackr(n,x,y); */ l1: t=rz; /* - - - - - - - - */ printf("\n %d ",t); goto jackr; /* начало фрагмента заменяющего функцию ackr */ ackr: u=( ST *) malloc( sizeof (ST) ); u->i=an; u->j=ax; u->k=ay; u->lr=l; u->pst=dl; dl=u; if (an==0||ay==0) dl->z=smacc(an,ax); else { an=dl->i; /* - замена вызова - */ ax=dl->j; /* */ ay=dl->k-1; /* z=ackr(n,x,y-1); */ l=2; /* */ goto ackr; /* */ l2: dl->z=rz; /* - - - - - - - - */ an=dl->i-1; /* - замена вызова - */ ax=rz; /* */ ay=dl->j; /* z=ackr(n-1,z,x); */ l=3; /* */ goto ackr; /* */ l3: dl->z=rz; /* - - - - - - - - */ } rz=dl->z; /* - - - - - - - - */ an=dl->i; /* */ ax=dl->j; /* замена */ ay=dl->k; /* */ l=dl->lr; /* оператора */ u=dl; /* */ dl=u->pst; /* return z ; */ free(u); /* */ switch(l) /* */ { case 1: goto l1; /* */ case 2: goto l2; /* */ case 3: goto l3; /* */ } /* - - - - - - - - */ jackr: } int smacc( int n,int x ) /* вспомогательная функция */ { switch (n) { case 0: return(x+1); case 1: return (x); case 2: return (0); case 3: return (1); default: return (2); } }

---

[ Назад | Оглавление ]

Рейтинги