C++: Mutual Recursion

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{align} 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{align}$

(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++ has prior declaration rules similar to those stated above for C, if we would use two functions. Instead here we define M and F as static (class) methods of a class, and specify the bodies inline in the declaration of the class. Inlined methods in the class can still call other methods or access fields in the class, no matter what order they are declared in, without any additional pre-declaration. This is possible because all the possible methods and fields are declared somewhere in the class declaration, which is known the first time the class declaration is parsed.

#include <iostream>
#include <vector>
#include <iterator>

class Hofstadter
{
public:
	static int F(int n) {
		if ( n == 0 ) return 1;
		return n - M(F(n-1));
	}
	static int M(int n) {
		if ( n == 0 ) return 0;
		return n - F(M(n-1));
	}
};

using namespace std;

int main()
{
	int i;
	vector<int> ra, rb;

	for(i=0; i < 20; i++) {
		ra.push_back(Hofstadter::F(i));
		rb.push_back(Hofstadter::M(i));
	}
	copy(ra.begin(), ra.end(),
	ostream_iterator<int>(cout, " "));
	cout << endl;
	copy(rb.begin(), rb.end(),
	ostream_iterator<int>(cout, " "));
	cout << endl;
	return 0;
}

The following version shows better what’s going on and why we seemingly didn’t need pre-declaration (like C) when “encapsulating” the functions as static (class) methods.
This version is equivalent to the above but does not inline the definition of the methods into the definition of the class. Here the method declarations in the class definition serves as the “pre-declaration” for the methods, as in C.

class Hofstadter
{
public:
	static int F(int n);
	static int M(int n);
};

int Hofstadter::F(int n)
{
	if ( n == 0 ) return 1;
	return n - M(F(n-1));
}

int Hofstadter::M(int n)
{
	if ( n == 0 ) return 0;
	return n - F(M(n-1));
}