Mutual Recursion allows us to take the fun of regular recursion (where a function calls itself until a terminating condition) and apply it to multiple functions calling each other! 

Let's use the Hofstadter Female and Male sequences to demonstrate this technique. You'll want to create two functions `F` and `M` such that the following equations are true: 

```
F(0) = 1
M(0) = 0
F(n) = n - M(F(n - 1))
M(n) = n - F(M(n - 1))
```

Don't worry about negative numbers, `n` will always be greater than or equal to zero.

~~~if:php,csharp
You *do* have to worry about performance though, mutual recursion uses up a lot of stack space (and is highly inefficient) so you may have to find a way to make your solution consume less stack space (and time).  Good luck :)
~~~

Hofstadter Wikipedia Reference http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences

Source: codewars | Difficulty: EASY
Tags: Mathematics

Complete search

Starter code: def f(n):
	

Solutions:
def f(n):
	return n - m(f(n - 1)) if n else 1

def m(n):
	return n - f(m(n - 1)) if n else 0


df = {0: 1}
dm = {0: 0}

def f(n):
	if n in df:
		return df[n]
	else:
		df[n] = n - m(f(n - 1))
		return df[n]

def m(n):
	if n in dm:
		return dm[n]
	else:
		dm[n] = n - f(m(n - 1))
		return dm[n]


f = lambda n: 1 if n == 0 else n - m(f(n - 1))
m = lambda n: 0 if n == 0 else n - f(m(n - 1))


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))
for i in range(10):
	print(i, f(i), m(i))


from functools import lru_cache

@lru_cache()
def f(n):
	return 1 if n <= 0 else n - m(f(n - 1))

@lru_cache()
def m(n):
	return 0 if n <= 0 else n - f(m(n - 1))