Sunday, December 23, 2012

Juggling with mutual recursion

Mutually recursive functions are not idiomatic in C, and can easily be avoided. However, they can be fun to play with. 

int f(int);
int g(int);

int f(int j)
{
   if (j > 0)
      return g(j-1);
   return 0;
}

int g(int j)
{
   if (j > 0)
      return f(j-2);
   return -1;
}

int main()
{
   return f(5);
}


Nothing remarkable here. The following, in contrast, doesn't work (at least not as expected).

int f(int j)
{
   if (j > 0)
      return g(j-1) - 2;   /* subtraction of -2 ignored */
}


As a proof of concept, here's a 2-D map which is iterated for as long as its coordinates stay in the first quadrant. In fact, the mutual recursion is here used for two alterating maps. It may appear that something strange such as this happens:

Actually, it's simpler:


void s(float x, float y);
void t(float x, float y);


void s(float x, float y)
{
   printf("s(%.5f, %.5f)\n", x, y);
   if(x >= 0.0 && y >= 0.0)
      
return t(x - 0.5, 1.2*y - .2*x);
}
void t(float x, float y)
{
   printf("t(%.5f, %.5f)\n", x, y);
  
if(x >= 0.0 && y >= 0.0)
      return s(1.2*x - .2*y, y-0.5);
}



This pair of functions differ by not using a return value as part of the recursion. Strange as it looks, it works.


No comments:

Post a Comment

I'm not home right now, but please leave a message and I'll get back to you in the next few years.