Mutual recursion

Mutual recursion
You are encouraged to solve this task according to the task description, using any language you may know.

Two functions are said to be mutually recursive if the first calls the second, and in turn the second calls the first.

Write two mutually recursive functions that compute members of the Hofstadter Female and Male sequences defined as:

${\begin{aligned}F(0)&=1\ ;\ M(0)=0\\F(n)&=n-M(F(n-1)),\quad n>0\\M(n)&=n-F(M(n-1)),\quad n>0.\end{aligned}}$

(If a language does not allow for a solution using mutually recursive functions then state this rather than give a solution by other means).

C

To let C see functions that will be used, it is enough to declare them. Normally this is done in a header file; in this example we do it directly in the code. If we do not declare them explicity, they get an implicit declaration (if implicit declaration matches the use, everything's fine; but it is better however write an explicit declaration)

<lang c>#include <stdio.h>

/* let us declare our functions; indeed here we need

  really only M declaration, so that F can "see" it
  and the compiler won't complain with a warning */

int F(int n); int M(int n);

int F(int n) {

 if ( n==0 ) return 1;
 return n - M(F(n-1));

}

int M(int n) {

 if ( n == 0 ) return 0;
 return n - F(M(n-1));

}

int main() {

 int i;

 for(i=0; i < 20; i++) {
   printf("%2d ", F(i));
 }
 printf("\n");
 for(i=0; i < 20; i++) {
   printf("%2d ", M(i));
 }
 printf("\n");
 return 0;

}</lang>

Python

Works with: Python version 3.0

.

Works with: Python version 2.6

<lang python>def F(n): return 1 if n == 0 else n - M(F(n-1)) def M(n): return 0 if n == 0 else n - F(M(n-1))

print ([ F(n) for n in range(20) ]) print ([ M(n) for n in range(20) ])</lang>

Output:

[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12]
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12]

In python there is no need to pre-declare M for it to be used in the definition of F. (However M must be defined before F calls it).