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>

Fortran

As far as the code of the two functions is inside the same "block" (module or program) we don't need special care. Otherwise, we should "load" at least the interface of the other function (each module will load mutually the other; of course the compiler won't enter in a infinite loop), e.g. by using a "use" (we do that if M and F function are inside different modules)

Works with: Fortran version 95 and later

<lang fortran>module MutualRec

 implicit none

contains

 pure recursive function m(n) result(r)
   integer :: r
   integer, intent(in) :: n
   if ( n == 0 ) then
      r = 0
      return
   end if
   r = n - f(m(n-1))
 end function m
 
 pure recursive function f(n) result(r)
   integer :: r
   integer, intent(in) :: n
   if ( n == 0 ) then
      r = 1
      return
   end if
   r = n - m(f(n-1))
 end function f

end module</lang>

I've added the attribute pure so that we can use them in a forall statement.

<lang fortran>program testmutrec

 use MutualRec
 implicit none

 integer :: i
 integer, dimension(20) :: a = (/ (i, i=0,19) /), b = (/ (i, i=0,19) /)
 integer, dimension(20) :: ra, rb
 
 forall(i=1:20) 
    ra(i) = m(a(i))
    rb(i) = f(b(i))
 end forall

 write(*,'(20I3)') rb
 write(*,'(20I3)') ra
 

end program testmutrec</lang>

Java

Translation of: C

<lang java5>public static int f(int n) {

 if ( n == 0 ) return 1;
 return n - m(f(n - 1));

}

public int m(int n) {

 if ( n == 0 ) return 0;
 return n - f(m(n - 1));

}

public static void main(String args[]){

  for(int i=0; i < 20; i++) {
     System.out.println(f(i));
  }
  System.out.println();
  for(i=0; i < 20; i++) {
     System.out.println(m(i));
  }

}</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).