Программирование на языке C



Рекурсия - часть 3


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 - целые неотрицательные числа.

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

/* рекурсивное вычисление функции Аккермана */ # include

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; }




Содержание  Назад  Вперед