Рекурсия
Следующая программа вычисляет функцию Аккермана с использованием рекурсивной функции
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;
}
Модифицируя функции 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);
}
}