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