jeniffer wrote:

Please give an example of 2 simple mutually recursive functions in C .

Here's one:

/************************************************** ****************/

#define F(Q,R,P) Q(int x){int i=x;while(i--)x=R(x,x);return x;}\

P(int L,int x){int i=x;if(L--)while(i--)x=P(L,x);return Q(x);}

#define Y(A,z,B,C,D,E,G,H,I,J,K,M,N,O,S,T,U,V,W)\

F(A,z,B)F(C,B,D)F(E,D,G)F(H,G,I)F(J,I,K)F(M,K,N)F( O,N,S)F(T,S,U)F(V,U,W)

Z(int L,int x)

{

int i = x;

if(L--)

while(i--)

x = Z(L,x);

return x << x;

}

Y(a,Z,b,c,d,e,g,h,X,j,k,m,n,o,s,t,u,v,w)

Y(Aa,w,Ba,Ca,Da,Ea,Ga,Ha,Ia,Ja,Ka,Ma,Na,Oa,Sa,Ta,U a,Va,Wa)

Y(Ab,Wa,Bb,Cb,Db,Eb,Gb,Hb,Ib,Jb,Kb,V,U,W,T,S,O,N,M )

F(A,M,B)

F(C,B,D)

F(E,D,G)

F(H,G,I)

F(J,I,K)

int main()

{

return K(99999,9);

}

/************************************************** *****************/

Here's David Moews' explanation of the code,

which is a better one than I could give,

except that by "outputs", he means "returns" :

{pete-4.c} uses the following set of recursive definitions

(generated by preprocessor abuse):

f(0,x) := x * (2**x),

g(m+1,0,x) := f(m,x),

g(m+1,n+1,x) := f(m,(g(m+1,n,?)@@x)(x)),

h(m,x) := g(m,x,x) (m > 0),

f(m,x) := (h(m,?)@@x)(x) (m > 0).

{pete-4.c} outputs g(33,99999,9).

The definition of g(m,n,x) is very similar to that of F[m,n](x),

and it is easy to prove that

F[n+2](x) <= g(1,n,x) <= F[n+2](x+2) (x > 0),

F[m,n+1](x) <= g(m+1,n,x) <= F[m,n+1](x+2) (m > 0, x > 0).

so

F[32,10**5](9) <= g(33,99999,9) <= F[32,10**5](11).

--

pete