# 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:

{\displaystyle {\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).

## ACL2

(mutual-recursion (defun f (n)    (declare (xargs :mode :program))    (if (zp n)        1        (- n (m (f (1- n))))))  (defun m (n)    (declare (xargs :mode :program))    (if (zp n)        0        (- n (f (m (1- n)))))))

with Ada.Text_Io; use Ada.Text_Io; procedure Mutual_Recursion is   function M(N : Integer) return Integer;   function F(N : Integer) return Integer is   begin      if N = 0 then         return 1;      else         return N - M(F(N - 1));      end if;   end F;   function M(N : Integer) return Integer is   begin      if N = 0 then         return 0;      else         return N - F(M(N-1));      end if;   end M;begin   for I in 0..19 loop      Put_Line(Integer'Image(F(I)));   end loop;   New_Line;   for I in 0..19 loop      Put_Line(Integer'Image(M(I)));   end loop;end Mutual_recursion;
with Ada.Text_Io; use Ada.Text_Io;procedure Mutual_Recursion is   function M(N: Natural) return Natural;   function F(N: Natural) return Natural;    function M(N: Natural) return Natural is       (if N = 0 then 0 else N – F(M(N–1)));    function F(N: Natural) return Natural is       (if N =0 then 1 else N – M(F(N–1)));begin   for I in 0..19 loop      Put_Line(Integer'Image(F(I)));   end loop;   New_Line;   for I in 0..19 loop      Put_Line(Integer'Image(M(I)));   end loop; end Mutual_recursion;

## Aime

Translation of: C
integer F(integer n);integer M(integer n); integer F(integer n){    integer r;    if (n) {	r = n - M(F(n - 1));    } else {	r = 1;    }    return r;} integer M(integer n){    integer r;    if (n) {	r = n - F(M(n - 1));    } else {	r = 0;    }    return r;} integer main(void){    integer i;    i = 0;    while (i < 20) {	o_winteger(3, F(i));	i += 1;    }    o_byte('\n');    i = 0;    while (i < 20) {	o_winteger(3, M(i));	i += 1;    }    o_byte('\n');    return 0;}

## ALGOL 68

Translation of: C
Works with: ALGOL 68 version Standard - no extensions to language used
Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386
PROC (INT)INT m; # ONLY required for ELLA ALGOL 68RS - an official subset OF full ALGOL 68 # PROC f = (INT n)INT:  IF n = 0 THEN 1  ELSE n - m(f(n-1)) FI; m := (INT n)INT:  IF n = 0 THEN 0  ELSE n - f(m(n-1)) FI; main:(  FOR i FROM 0 TO 19 DO    print(whole(f(i),-3))  OD;  new line(stand out);  FOR i FROM 0 TO 19 DO    print(whole(m(i),-3))  OD;  new line(stand out))
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


## ALGOL W

begin    % define mutually recursive funtions F and M that compute the elements   %    % of the Hofstadter Female and Male sequences                            %     integer procedure F ( integer value n ) ;        if n = 0 then 1 else n - M( F( n - 1 ) );     integer procedure M ( integer value n ) ;        if n = 0 then 0 else n - F( M( n - 1 ) );     % print the first few elements of the sequences                          %    i_w := 2; s_w := 1; % set I/O formatting                                 %    write( "F: " );    for i := 0 until 20 do writeon( F( i ) );    write( "M: " );    for i := 0 until 20 do writeon( M( i ) ); end.

## AutoHotkey

Loop 20   i := A_Index-1, t .= "n" i "t   " M(i) "t     " F(i)MsgBox xtmaletfemalen%t% F(n) {   Return n ? n - M(F(n-1)) : 1} M(n) {   Return n ? n - F(M(n-1)) : 0}
Translation of: C

This one is an alternative to the above.

main()Return F(n){  If (n == 0)     Return 1  Else    Return n - M(F(n-1))} M(n){  If (n == 0)    Return 0  Else    Return n - F(M(n-1)) ;} main(){  i = 0  While, i < 20  {    male .= M(i) . "n"     female .= F(i) . "n"    i++  }  MsgBox % "male:n" . male  MsgBox % "female:n" . female}

## AWK

In AWK it is enough that both functions are defined somewhere. It matters not whether the BEGIN block is before or after the function definitions.

function F(n){  if ( n == 0 ) return 1;  return n - M(F(n-1))} function M(n){  if ( n == 0 ) return 0;  return n - F(M(n-1))} BEGIN {  for(i=0; i < 20; i++) {    printf "%3d ", F(i)  }  print ""  for(i=0; i < 20; i++) {    printf "%3d ", M(i)  }  print ""}

## BASIC

Works with: QBasic
DECLARE FUNCTION f! (n!)DECLARE FUNCTION m! (n!) FUNCTION f! (n!)    IF n = 0 THEN        f = 1    ELSE        f = m(f(n - 1))    END IFEND FUNCTION FUNCTION m! (n!)    IF n = 0 THEN        m = 0    ELSE        m = f(m(n - 1))    END IFEND FUNCTION

## BBC BASIC

      @% = 3 : REM Column width      PRINT "F sequence:"      FOR i% = 0 TO 20        PRINT FNf(i%) ;      NEXT      PRINT      PRINT "M sequence:"      FOR i% = 0 TO 20        PRINT FNm(i%) ;      NEXT      PRINT      END       DEF FNf(n%) IF n% = 0 THEN = 1 ELSE = n% - FNm(FNf(n% - 1))       DEF FNm(n%) IF n% = 0 THEN = 0 ELSE = n% - FNf(FNm(n% - 1))
Output:
F sequence:
1  1  2  2  3  3  4  5  5  6  6  7  8  8  9  9 10 11 11 12 13
M sequence:
0  0  1  2  2  3  4  4  5  6  6  7  7  8  9  9 10 11 11 12 12


## Bc

define f(n) {  if ( n == 0 ) return(1);  return(n - m(f(n-1)));} define m(n) {  if ( n == 0 ) return(0);  return(n - f(m(n-1)));}
Works with: GNU bc
Works with: OpenBSD bc

POSIX bc doesn't have the print statement.

/* GNU bc */for(i=0; i < 19; i++) {  print f(i); print " ";}print "\n";for(i=0; i < 19; i++) {  print m(i); print " ";}print "\n";

## Bracmat

 (F=.!arg:0&1|!arg+-1*M$(F$(!arg+-1))); (M=.!arg:0&0|!arg+-1*F$(M$(!arg+-1)));  -1:?n&whl'(!n+1:~>20:?n&put$(F$!n " "))&put$\n 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 -1:?n&whl'(!n+1:~>20:?n&put$(M$!n " "))&put$\n 0  0  1  2  2  3  4  4  5  6  6  7  7  8  9  9  10  11  11  12  12

## Brat

female = null #yes, this is necessary male = { n |  true? n == 0    { 0 }    { n - female male(n - 1) }} female = { n |  true? n == 0    { 1 }    { n - male female(n - 1 ) }} p 0.to(20).map! { n | female n }p 0.to(20).map! { n | male n }

## 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 explicitly, they get an implicit declaration (if implicit declaration matches the use, everything's fine; but it is better however to write an explicit declaration)

#include <stdio.h>#include <stdlib.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(const int n);int M(const int n); int F(const int n){  return (n == 0) ? 1 : n - M(F(n - 1));} int M(const int n){  return (n == 0) ? 0 : n - F(M(n - 1));} int main(void){  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 EXIT_SUCCESS;}

## C++

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));}

## C#

namespace RosettaCode {    class Hofstadter {        static public int F(int n) {            int result = 1;            if (n > 0) {                result = n - M(F(n-1));            }             return result;        }         static public int M(int n) {            int result = 0;            if (n > 0) {                result = n - F(M(n - 1));            }             return result;        }    }}

## Ceylon

Integer f(Integer n)    =>  if (n > 0)        then n - m(f(n-1))        else 1; Integer m(Integer n)    =>  if (n > 0)        then n - f(m(n-1))        else 0; shared void run() {    printAll((0:20).map(f));    printAll((0:20).map(m));}
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


## Clojure

(declare F) ; forward reference  (defn M [n]  (if (zero? n)    0    (- n (F (M (dec n)))))) (defn F [n]  (if (zero? n)    1    (- n (M (F (dec n))))))

## CoffeeScript

 F = (n) ->  if n is 0 then 1 else n - M F n - 1 M = (n) ->  if n is 0 then 0 else n - F M n - 1 console.log [0...20].map Fconsole.log [0...20].map M
Output:
 > coffee mutual_recurse.coffee [ 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 ]

## Common Lisp

(defun m (n)    (if (zerop n)        0        (- n (f (m (- n 1)))))) (defun f (n)    (if (zerop n)        1        (- n (m (f (- n 1))))))

## D

import std.stdio, std.algorithm, std.range; int male(in int n) pure nothrow {    return n ? n - male(n - 1).female : 0;} int female(in int n) pure nothrow {    return n ? n - female(n - 1).male : 1;} void main() {    20.iota.map!female.writeln;    20.iota.map!male.writeln;}
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]

## Déjà Vu

F n:	if n:		- n M F -- n	else:		1 M n:	if n:		- n F M -- n	else:		0 for i range 0 10:	!.( M i F i )
Output:
0 1
0 1
1 2
2 2
2 3
3 3
4 4
4 5
5 5
6 6
6 6 

## Dart

int M(int n) => n==0?1:n-F(M(n-1));int F(int n) => n==0?0:n-M(F(n-1)); main() {  String f="",m="";  for(int i=0;i<20;i++) {    m+="${M(i)} "; f+="${F(i)} ";  }  print("M: $m"); print("F:$f");}

## Delphi

 unit Hofstadter; interface type  THofstadterFemaleMaleSequences = class  public    class function F(n: Integer): Integer;    class function M(n: Integer): Integer;  end; implementation class function THofstadterFemaleMaleSequences.F(n: Integer): Integer;begin  Result:= 1;  if (n > 0) then    Result:= n - M(F(n-1));end; class function THofstadterFemaleMaleSequences.M(n: Integer): Integer;begin  Result:= 0;  if (n > 0) then    Result:= n - F(M(n - 1));end; end.

## E

In E, nouns (variable names) always refer to preceding definitions, so to have mutual recursion, either one must be forward-declared or we must use a recursive def construct. Either one of these is syntactic sugar for first binding the noun to an E promise (a reference with an undetermined target), then resolving the promise to the value.

Recursive def:

def [F, M] := [  fn n { if (n <=> 0) { 1 } else { n - M(F(n - 1)) } },  fn n { if (n <=> 0) { 0 } else { n - F(M(n - 1)) } },]

Forward declaration:

def Mdef  F(n) { return if (n <=> 0) { 1 } else { n - M(F(n - 1)) } }bind M(n) { return if (n <=> 0) { 0 } else { n - F(M(n - 1)) } }

def M binds M to a promise, and stashes the resolver for that promise where bind can get to it. When def F... is executed, the function F closes over the promise which is the value of M. bind M... uses the resolver to resolve M to the provided definition. The recursive def operates similarly, except that it constructs promises for every variable on the left side ([F, M]), executes the right side ([fn ..., fn ...]) and collects the values, then resolves each promise to its corresponding value.

But you don't have to worry about that to use it.

## Eiffel

 class	APPLICATION create	make feature 	make			-- Test of the mutually recursive functions Female and Male.		do			across				0 |..| 19 as c			loop				io.put_string (Female (c.item).out + " ")			end			io.new_line			across				0 |..| 19 as c			loop				io.put_string (Male (c.item).out + " ")			end		end 	Female (n: INTEGER): INTEGER			-- Female sequence of the Hofstadter Female and Male sequences.		require			n_not_negative: n >= 0		do			Result := 1			if n /= 0 then				Result := n - Male (Female (n - 1))			end		end 	Male (n: INTEGER): INTEGER			-- Male sequence of the Hofstadter Female and Male sequences.		require			n_not_negative: n >= 0		do			Result := 0			if n /= 0 then				Result := n - Female (Male (n - 1))			end		end end
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


## Elixir

defmodule MutualRecursion do  def f(0), do: 1  def f(n), do: n - m(f(n - 1))   def m(0), do: 0  def m(n), do: n - f(m(n - 1)) end IO.inspect Enum.map(0..19, fn n -> MutualRecursion.f(n) end)IO.inspect Enum.map(0..19, fn n -> MutualRecursion.m(n) end)
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]


## Erlang

-module(mutrec).-export([mutrec/0, f/1, m/1]). f(0) -> 1;f(N) -> N - m(f(N-1)). m(0) -> 0;m(N) -> N - f(m(N-1)). mutrec() -> lists:map(fun(X) -> io:format("~w ", [f(X)]) end, lists:seq(0,19)),	    io:format("~n", []),	    lists:map(fun(X) -> io:format("~w ", [m(X)]) end, lists:seq(0,19)),	    io:format("~n", []).

## Euphoria

integer idM, idF function F(integer n)    if n = 0 then        return 1    else        return n - call_func(idM,{F(n-1)})    end ifend function idF = routine_id("F") function M(integer n)    if n = 0 then        return 0    else        return n - call_func(idF,{M(n-1)})    end ifend function idM = routine_id("M")

## F#

let rec f n =    match n with    | 0 -> 1    | _ -> n - (m (f (n-1)))and m n =    match n with    | 0 -> 0    | _ -> n - (f (m (n-1)))

Like OCaml, the let rec f .. and m ... construct indicates that the functions call themselves (rec) and each other (and).

## Factor

In Factor, if you need a word before it's defined, you have to DEFER: it.

DEFER: F: M ( n -- n' ) dup 0 = [ dup 1 - M F - ] unless ;: F ( n -- n' ) dup 0 = [ drop 1 ] [ dup 1 - F M - ] if ;

## Julia

F(n) = n < 1 ? one(n) : n - M(F(n - 1))M(n) = n < 1 ? zero(n) : n - F(M(n - 1))
Output:
julia> [F(i) for i = 0:19], [M(i) for i = 0:19]
([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])


## Liberty BASIC

 print "F sequence."for i = 0 to 20print f(i);" ";nextprintprint "M sequence."for i = 0 to 20print m(i);" ";next end function f(n)    if n = 0 then        f = 1    else        f = n - m(f(n - 1))    end if    end function function m(n)    if n = 0 then        m = 0    else        m = n - f(m(n - 1))    end if    end function
Output:
F sequence.
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13
M sequence.
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12

## LibreOffice Basic

'// LibreOffice Basic Implementation of Hofstadter Female-Male sequences '// Utility functionssub setfont(strfont)	ThisComponent.getCurrentController.getViewCursor.charFontName = strfontend sub sub newline	oVC = thisComponent.getCurrentController.getViewCursor	oText = oVC.text	oText.insertControlCharacter(oVC, com.sun.star.text.ControlCharacter.PARAGRAPH_BREAK, False)end sub sub out(sString)	oVC = ThisComponent.getCurrentController.getViewCursor	oText = oVC.text	oText.insertString(oVC, sString, false)end sub sub outln(optional sString)	if not ismissing (sString) then out(sString)	newlineend sub function intformat(n as integer,nlen as integer) as string	dim nstr as string	nstr = CStr(n)	while len(nstr) < nlen		nstr = " " & nstr	wend	intformat = nstrend function '// Hofstadter Female-Male function definitionsfunction F(n as long) as long	if n = 0 Then		F =  1	elseif n > 0 Then		F = n - M(F(n - 1))	endif end function function M(n)	if n = 0 Then		M = 0	elseif n > 0 Then		M = n - F(M(n - 1))	endif end function '// Hofstadter Female Male sequence demo routinesub Hofstadter_Female_Male_Demo	'// Introductory Text	setfont("LM Roman 10")	outln("Rosetta Code Hofstadter Female and Male Sequence Challenge")	outln	out("Two functions are said to be mutually recursive if the first calls the second,")	outln(" and in turn the second calls the first.")	out("Write two mutually recursive functions that compute members of the Hofstadter")	outln(" Female and Male sequences defined as:")	outln	setfont("LM Mono Slanted 10")	outln(chr(9)+"F(0) = 1 ; M(0)=0")	outln(chr(9)+"F(n) = n - M(F(n-1)), n > 0")	outln(chr(9)+"M(n) = n - F(M(n-1)), n > 0")	outln	'// Sequence Generation	const nmax as long = 20	dim n as long	setfont("LM Mono 10")	out("n    = "	for n = 0 to nmax		out(" " + intformat(n, 2))	next n	outln	out("F(n) = " 	for n = 0 to nmax		out(" " + intformat(F(n),2))	next n	outln	out("M(n) = " 	for n = 0 to nmax		out(" " + intformat(M(n), 2))	next n	outln end sub ------------------------------Output------------------------------n    =   0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20F(n) =   1  1  2  2  3  3  4  5  5  6  6  7  8  8  9  9 10 11 11 12 13M(n) =   0  0  1  2  2  3  4  4  5  6  6  7  7  8  9  9 10 11 11 12 12

## Logo

Like Lisp, symbols in Logo are late-bound so no special syntax is required for forward references.

to m :n  if 0 = :n [output 0]  output :n - f m :n-1endto f :n  if 0 = :n [output 1]  output :n - m f :n-1end show cascade 20 [lput m #-1 ?] [][1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12]show cascade 20 [lput f #-1 ?] [][0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12]

## LSL

To test it yourself; rez a box on the ground, and add the following as a New Script.

integer iDEPTH = 100;integer f(integer n) {	if(n==0) {		return 1;	} else {		return n-m(f(n - 1));	}}integer m(integer n) {	if(n==0) {		return 0;	} else {		return n-f(m(n - 1));	}}default {	state_entry() {		integer x = 0;		string s = "";		for(x=0 ; x<iDEPTH ; x++) {			s += (string)(f(x))+" ";		}		llOwnerSay(llList2CSV(llParseString2List(s, [" "], [])));		s = "";		for(x=0 ; x<iDEPTH ; x++) {			s += (string)(m(x))+" ";		}		llOwnerSay(llList2CSV(llParseString2List(s, [" "], [])));	}}
Output:
1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 34, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47, 48, 48, 49, 50, 50, 51, 51, 52, 53, 53, 54, 55, 55, 56, 56, 57, 58, 58, 59, 59, 60, 61, 61
0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 20, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47, 48, 48, 49, 50, 50, 51, 51, 52, 53, 53, 54, 54, 55, 56, 56, 57, 58, 58, 59, 59, 60, 61, 61

## Lua

 function m(n) return n > 0 and n - f(m(n-1)) or 0 endfunction f(n) return n > 0 and n - m(f(n-1)) or 1 end

It is important to note, that if m and f are to be locally scoped functions rather than global, that they would need to be forward declared:

 local m,nfunction m(n) return n > 0 and n - f(m(n-1)) or 0 endfunction f(n) return n > 0 and n - m(f(n-1)) or 1 end

define(female',ifelse(0,$1,1,eval($1 - male(female(decr($1))))')')dnldefine(male',ifelse(0,$1,0,eval($1 - female(male(decr($1))))')')dnldefine(loop',ifelse($1,$2,,$3($1) loop(incr($1),$2,$3')')')dnlloop(0,20,female')loop(0,20,male') ## Mathematica Without caching: f[0]:=1m[0]:=0f[n_]:=n-m[f[n-1]]m[n_]:=n-f[m[n-1]] With caching: f[0]:=1m[0]:=0f[n_]:=f[n]=n-m[f[n-1]]m[n_]:=m[n]=n-f[m[n-1]] Example finding f(1) to f(30) and m(1) to m(30): m /@ Range[30] f /@ Range[30] gives back: {0,1,2,2,3,4,4,5,6,6,7,7,8,9,9,10,11,11,12,12,13,14,14,15,16,16,17,17,18,19}{1,2,2,3,3,4,5,5,6,6,7,8,8,9,9,10,11,11,12,13,13,14,14,15,16,16,17,17,18,19} ## MATLAB female.m: function Fn = female(n) if n == 0 Fn = 1; return end Fn = n - male(female(n-1));end male.m: function Mn = male(n) if n == 0 Mn = 0; return end Mn = n - female(male(n-1));end Output: >> n = (0:10);>> arrayfun(@female,n) ans = 1 1 2 2 3 3 4 5 5 6 6 >> arrayfun(@male,n) ans = 0 0 1 2 2 3 4 4 5 6 6 ## Maxima f[0]: 1$m[0]: 0$f[n] := n - m[f[n - 1]]$m[n] := n - f[m[n - 1]]$makelist(f[i], i, 0, 10);[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6] makelist(m[i], i, 0, 10);[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6] remarray(m, f)$ f(n) := if n = 0 then 1 else n - m(f(n - 1))$m(n) := if n = 0 then 0 else n - f(m(n - 1))$ makelist(f(i), i, 0, 10);[1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6] makelist(m(i), i, 0, 10);[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6] remfunction(f, m)$ ## Mercury  :- module mutual_recursion.:- interface. :- import_module io.:- pred main(io::di, io::uo) is det. :- implementation.:- import_module int, list. main(!IO) :- io.write(list.map(f, 0..19), !IO), io.nl(!IO), io.write(list.map(m, 0..19), !IO), io.nl(!IO). :- func f(int) = int. f(N) = ( if N = 0 then 1 else N - m(f(N - 1)) ). :- func m(int) = int. m(N) = ( if N = 0 then 0 else N - f(m(N - 1)) ).  ## MMIX  LOC Data_Segment GREG @NL BYTE #a,0 GREG @buf OCTA 0,0 t IS$128Ja	IS	$127 LOC #1000 GREG @// print 2 digits integer with trailing space to StdOut// reg$3 contains int to be printedbp	IS	$710H GREG #0000000000203020 prtInt STO 0B,buf % initialize buffer LDA bp,buf+7 % points after LSD % REPEAT1H SUB bp,bp,1 % move buffer pointer DIV$3,$3,10 % divmod (x,10) GET t,rR % get remainder INCL t,'0' % make char digit STB t,bp % store digit PBNZ$3,1B		% UNTIL no more digits	LDA	$255,bp TRAP 0,Fputs,StdOut % print integer GO Ja,Ja,0 % 'return'// Female functionF GET$1,rJ		% save return addr	PBNZ	$0,1F % if N != 0 then F N INCL$0,1		% F 0 = 1	PUT	rJ,$1 % restore return addr POP 1,0 % return 11H SUBU$3,$0,1 % N1 = N - 1 PUSHJ$2,F		% do F (N - 1) 	ADDU	$3,$2,0		% place result in arg. reg.	PUSHJ	$2,M % do M F ( N - 1) PUT rJ,$1		% restore ret addr	SUBU	$0,$0,$2 POP 1,0 % return N - M F ( N - 1 )// Male functionM GET$1,rJ	PBNZ	$0,1F PUT rJ,$1	POP	1,0		% return M 0 = 01H	SUBU	$3,$0,1	PUSHJ	$2,M ADDU$3,$2,0 PUSHJ$2,F	PUT	rJ,$1 SUBU$0,$0,$2	POP	1,0		$return N - F M ( N - 1 )// do a female runMain SET$1,0		% for (i=0; i<25; i++){1H	ADDU	$4,$1,0		%	PUSHJ	$3,F % F (i) GO Ja,prtInt % print F (i) INCL$1,1	CMP	t,$1,25 PBNZ t,1B % } LDA$255,NL	TRAP	0,Fputs,StdOut// do a male run	SET	$1,0 % for (i=0; i<25; i++){1H ADDU$4,$1,0 % PUSHJ$3,M		%  M (i)	GO	Ja,prtInt	%  print M (i)	INCL	$1,1 CMP t,$1,25	PBNZ	t,1B		% }	LDA	$255,NL TRAP 0,Fputs,StdOut TRAP 0,Halt,0 Output: ~/MIX/MMIX/Rosetta> mmix mutualrecurs1 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 13 14 14 15 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12 13 14 14 15  ## Nemerle using System;using System.Console; module Hofstadter{ F(n : int) : int { |0 => 1 |_ => n - M(F(n - 1)) } M(n : int) : int { |0 => 0 |_ => n - F(M(n - 1)) } Main() : void { foreach (n in [0 .. 20]) Write("{0} ", F(n)); WriteLine(); foreach (n in [0 .. 20]) Write("{0} ", M(n)); }} ## Nim proc m(n): int proc f(n): int = if n == 0: 1 else: n - m(f(n-1)) proc m(n): int = if n == 0: 0 else: n - f(m(n-1)) for i in 1 .. 10: echo f(i) echo m(i) ## Objective-C Objective-C has prior declaration rules similar to those stated above for C, for C-like types. In this example we show the use of a two class method; this works since we need an interface block that is like declaration of functions in C code. #import <Foundation/Foundation.h> @interface Hofstadter : NSObject+ (int)M: (int)n;+ (int)F: (int)n;@end @implementation Hofstadter+ (int)M: (int)n{ if ( n == 0 ) return 0; return n - [self F: [self M: (n-1)]];}+ (int)F: (int)n{ if ( n == 0 ) return 1; return n - [self M: [self F: (n-1)]];}@end int main(){ int i; for(i=0; i < 20; i++) { printf("%3d ", [Hofstadter F: i]); } printf("\n"); for(i=0; i < 20; i++) { printf("%3d ", [Hofstadter M: i]); } printf("\n"); return 0;} ## Objeck Translation of: C  class MutualRecursion { function : Main(args : String[]) ~ Nil { for(i := 0; i < 20; i+=1;) { f(i)->PrintLine(); }; "---"->PrintLine(); for (i := 0; i < 20; i+=1;) { m(i)->PrintLine(); }; } function : f(n : Int) ~ Int { return n = 0 ? 1 : n - m(f(n - 1)); } function : m(n : Int) ~ Int { return n = 0 ? 0 : n - f(m(n - 1)); }}  ## OCaml let rec f = function | 0 -> 1 | n -> n - m(f(n-1))and m = function | 0 -> 0 | n -> n - f(m(n-1));; The let rec f ... and m ... construct indicates that the functions call themselves (rec) and each other (and). ## Octave We don't need to pre-declare or specify in some other way a function that will be defined later; but both must be declared before their use. (The code is written to handle vectors, as the testing part shows) function r = F(n) for i = 1:length(n) if (n(i) == 0) r(i) = 1; else r(i) = n(i) - M(F(n(i)-1)); endif endforendfunction function r = M(n) for i = 1:length(n) if (n(i) == 0) r(i) = 0; else r(i) = n(i) - F(M(n(i)-1)); endif endforendfunction # testingra = F([0:19]);rb = M([0:19]);disp(ra);disp(rb); ## Oforth Oforth can declare methods objects without any implementation. This allows to implement mutual recursion. This does not work with functions (declaration and implementation must be together). Method new: M Integer method: F{ self 0 == ifTrue: [ 1 return ] self self 1 - F M -} Integer method: M{ self 0 == ifTrue: [ 0 return ] self self 1 - M F -} seqFrom(0, 20) map(#F) printlnseqFrom(0, 20) map(#M) println Output: [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13] [0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12]  ## Order Since Order is powered by the C preprocessor, definitions follow the same rule as CPP macros: they can appear in any order relative to each other as long as all are defined before the ORDER_PP block that calls them. #include <order/interpreter.h> #define ORDER_PP_DEF_8f \ORDER_PP_FN(8fn(8N, \ 8if(8is_0(8N), \ 1, \ 8sub(8N, 8m(8f(8dec(8N))))))) #define ORDER_PP_DEF_8m \ORDER_PP_FN(8fn(8N, \ 8if(8is_0(8N), \ 0, \ 8sub(8N, 8f(8m(8dec(8N))))))) //TestORDER_PP(8for_each_in_range(8fn(8N, 8print(8f(8N))), 0, 19))ORDER_PP(8for_each_in_range(8fn(8N, 8print(8m(8N))), 0, 19)) ## Oz declare fun {F N} if N == 0 then 1 elseif N > 0 then N - {M {F N-1}} end end fun {M N} if N == 0 then 0 elseif N > 0 then N - {F {M N-1}} end endin {Show {Map {List.number 0 9 1} F}} {Show {Map {List.number 0 9 1} M}} ## PARI/GP F(n)=if(n,n-M(F(n-1)),1)M(n)=if(n,n-F(M(n-1)),0) ## Pascal In Pascal we need to pre-declare functions/procedures; to do so, the forward statement is used. Program MutualRecursion; {M definition comes after F which uses it}function M(n : Integer) : Integer; forward; function F(n : Integer) : Integer;begin if n = 0 then F := 1 else F := n - M(F(n-1));end; function M(n : Integer) : Integer;begin if n = 0 then M := 0 else M := n - F(M(n-1));end; var i : Integer; begin for i := 0 to 19 do begin write(F(i) : 4) end; writeln; for i := 0 to 19 do begin write(M(i) : 4) end; writeln;end. ## Perl sub F { my$n = shift; $n ?$n - M(F($n-1)) : 1 }sub M { my$n = shift; $n ?$n - F(M($n-1)) : 0 } # Usage:foreach my$sequence (\&F, \&M) {    print join(' ', map $sequence->($_), 0 .. 19), "\n";}
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


## Perl 6

A direct translation of the definitions of ${\displaystyle F}$ and ${\displaystyle M}$:

multi F(0) { 1 }; multi M(0) { 0 }multi F(\𝑛) { 𝑛 - M(F(𝑛 - 1)) }multi M(\𝑛) { 𝑛 - F(M(𝑛 - 1)) } say map &F, ^20;say map &M, ^20;
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


## Phix

function F(integer n)    return iff(n?n-M(F(n-1)):1)end function function M(integer n)    return iff(n?n-F(M(n-1)):0)end function for i=0 to 20 do    printf(1," %d",F(i))end forprintf(1,"\n")for i=0 to 20 do    printf(1," %d",M(i))end for

You can also explicitly declare forward routines, which may sometimes be necessary for routines with optional or named parameters, or just make something easier to understand.

forward function F(integer n)forward function M(integer n)
Output:
 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12


## PHP

<?phpfunction F($n){ if ($n == 0 ) return 1;  return $n - M(F($n-1));} function M($n){ if ($n == 0) return 0;  return $n - F(M($n-1));} $ra = array();$rb = array();for($i=0;$i < 20; $i++){ array_push($ra, F($i)); array_push($rb, M($i));}echo implode(" ",$ra) . "\n";echo implode(" ", $rb) . "\n";?> ## PicoLisp (de f (N) (if (=0 N) 1 (- N (m (f (dec N)))) ) ) (de m (N) (if (=0 N) 0 (- N (f (m (dec N)))) ) ) ## PL/I  test: procedure options (main); M: procedure (n) returns (fixed) recursive; /* 8/1/2010 */ declare n fixed; if n <= 0 then return (0); else return ( n - F(M(n-1)) );end M; F: procedure (n) returns (fixed) recursive; declare n fixed; if n <= 0 then return (1); else return ( n - M(F(n-1)) );end F; declare i fixed; do i = 1 to 15; put skip list ( F(i), M(i) ); end;end test;  ## PostScript  /female{/n exch defn 0 eq{1}{n n 1 sub female male sub}ifelse}def /male{/n exch defn 0 eq{0}{n n 1 sub male female sub}ifelse}def  Library: initlib  /F {{ {0 eq} {pop 1} is? {0 gt} {dup 1 sub F M sub} is?} cond}. /M {{ {0 eq} {pop 0} is? {0 gt} {dup 1 sub M F sub} is?} cond}.  ## PowerShell function F($n) {    if ($n -eq 0) { return 1 } return$n - (M (F ($n - 1)))} function M($n) {    if ($n -eq 0) { return 0 } return$n - (F (M ($n - 1)))} ## Prolog female(0,1).female(N,F) :- N>0, N1 is N-1, female(N1,R), male(R, R1), F is N-R1. male(0,0).male(N,F) :- N>0, N1 is N-1, male(N1,R), female(R, R1), F is N-R1. Works with: GNU Prolog flist(S) :- for(X, 0, S), female(X, R), format('~d ', [R]), fail.mlist(S) :- for(X, 0, S), male(X, R), format('~d ', [R]), fail. Testing | ?- flist(19). 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 no | ?- mlist(19). 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 ## Pure The Pure definitions very closely maps to the mathematical definitions. F 0 = 1;M 0 = 0;F n = n - M(F(n-1)) if n>0;M n = n - F(M(n-1)) if n>0; > let females = map F (0..10); females;[1,1,2,2,3,3,4,5,5,6,6]> let males = map M (0..10); males;[0,0,1,2,2,3,4,4,5,6,6] ## PureBasic Declare M(n) Procedure F(n) If n = 0 ProcedureReturn 1 ElseIf n > 0 ProcedureReturn n - M(F(n - 1)) EndIf EndProcedure Procedure M(n) If n = 0 ProcedureReturn 0 ElseIf n > 0 ProcedureReturn n - F(M(n - 1)) EndIf EndProcedure Define iIf OpenConsole() For i = 0 To 19 Print(Str(F(i))) If i = 19 Continue EndIf Print(", ") Next PrintN("") For i = 0 To 19 Print(Str(M(i))) If i = 19 Continue EndIf Print(", ") Next Print(#CRLF$ + #CRLF+ "Press ENTER to exit") Input() CloseConsole()EndIf 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 ## Python Works with: Python version 3.0 . Works with: Python version 2.6 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) ]) 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). ## R F <- function(n) ifelse(n == 0, 1, n - M(F(n-1)))M <- function(n) ifelse(n == 0, 0, n - F(M(n-1))) print.table(lapply(0:19, M))print.table(lapply(0:19, F)) ## REBOL rebol [ Title: "Mutual Recursion" Date: 2009-12-14 Author: oofoe URL: http://rosettacode.org/wiki/Mutual_Recursion References: [http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences]] f: func [ "Female." n [integer!] "Value."] [either 0 = n [1][n - m f n - 1]] m: func [ "Male." n [integer!] "Value."] [either 0 = n [0][n - f m n - 1]] fs: [] ms: [] for i 0 19 1 [append fs f i append ms m i]print ["F:" mold fs crlf "M:" mold ms] Output: F: [1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12] M: [0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12] ## Racket #lang racket(define (F n) (if (>= 0 n) 1 (- n (M (F (sub1 n)))))) (define (M n) (if (>= 0 n) 0 (- n (F (M (sub1 n)))))) ## REXX ### vanilla This version uses vertical formatting of the output. /*REXX program shows mutual recursion (via Hofstadter Male & Female sequence).*/parse arg lim .; if lim='' then lim=40; w=length(lim); pad=left('',20) do j=0 to lim; jj=right(j,w); ff=right(F(j),w); mm=right(M(j),w) say pad 'F('jj") =" ff pad 'M('jj") =" mm end /*j*/exit /*stick a fork in it, we're all done. *//*────────────────────────────────────────────────────────────────────────────*/F: procedure; parse arg n; if n==0 then return 1; return n - M(F(n-1))M: procedure; parse arg n; if n==0 then return 0; return n - F(M(n-1)) output when using the default input of: 40  F( 0) = 1 M( 0) = 0 F( 1) = 1 M( 1) = 0 F( 2) = 2 M( 2) = 1 F( 3) = 2 M( 3) = 2 F( 4) = 3 M( 4) = 2 F( 5) = 3 M( 5) = 3 F( 6) = 4 M( 6) = 4 F( 7) = 5 M( 7) = 4 F( 8) = 5 M( 8) = 5 F( 9) = 6 M( 9) = 6 F(10) = 6 M(10) = 6 F(11) = 7 M(11) = 7 F(12) = 8 M(12) = 7 F(13) = 8 M(13) = 8 F(14) = 9 M(14) = 9 F(15) = 9 M(15) = 9 F(16) = 10 M(16) = 10 F(17) = 11 M(17) = 11 F(18) = 11 M(18) = 11 F(19) = 12 M(19) = 12 F(20) = 13 M(20) = 12 F(21) = 13 M(21) = 13 F(22) = 14 M(22) = 14 F(23) = 14 M(23) = 14 F(24) = 15 M(24) = 15 F(25) = 16 M(25) = 16 F(26) = 16 M(26) = 16 F(27) = 17 M(27) = 17 F(28) = 17 M(28) = 17 F(29) = 18 M(29) = 18 F(30) = 19 M(30) = 19 F(31) = 19 M(31) = 19 F(32) = 20 M(32) = 20 F(33) = 21 M(33) = 20 F(34) = 21 M(34) = 21 F(35) = 22 M(35) = 22 F(36) = 22 M(36) = 22 F(37) = 23 M(37) = 23 F(38) = 24 M(38) = 24 F(39) = 24 M(39) = 24 F(40) = 25 M(40) = 25  ### with memoization This version uses memoization as well as a horizontal (aligned) output format. The optimization due to memoization is faster by many orders of magnitude. /*REXX program shows mutual recursion (via Hofstadter Male & Female sequence).*/parse arg lim .; if lim=='' then lim=40 /*assume the default for LIM? */w=length(lim);m.=.;   $m.0=0;$f.=.;   $f.0=1; Js=; Fs=; Ms= do j=0 to lim Js=Js right(j,w); Fs=Fs right(F(j),w); Ms=Ms right(M(j),w) end /*j*/say 'Js=' Js /*display the list of Js to the term.*/say 'Fs=' Fs /* " " " " Fs " " " */say 'Ms=' Ms /* " " " " Ms " " " */exit /*stick a fork in it, we're all done. *//*───────────────────────────────────────────────────────────────────────────────────*/F: procedure expose$m. $f.; parse arg n; if$f.n==. then $f.n=n-M(F(n-1)); return$f.nM: procedure expose $m.$f.; parse arg n; if $m.n==. then$m.n=n-F(M(n-1)); return $m.n output when using the default input of: 99 Js= 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 Fs= 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 13 14 14 15 16 16 17 17 18 19 19 20 21 21 22 22 23 24 24 25 25 26 27 27 28 29 29 30 30 31 32 32 33 34 34 35 35 36 37 37 38 38 39 40 40 41 42 42 43 43 44 45 45 46 46 47 48 48 49 50 50 51 51 52 53 53 54 55 55 56 56 57 58 58 59 59 60 61 61 Ms= 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12 13 14 14 15 16 16 17 17 18 19 19 20 20 21 22 22 23 24 24 25 25 26 27 27 28 29 29 30 30 31 32 32 33 33 34 35 35 36 37 37 38 38 39 40 40 41 42 42 43 43 44 45 45 46 46 47 48 48 49 50 50 51 51 52 53 53 54 54 55 56 56 57 58 58 59 59 60 61 61  ### with memoization, specific entry This version is identical in function to the previous example, but it also can compute and display a specific request (indicated by a negative number for the argument). /*REXX program shows mutual recursion (via Hofstadter Male & Female sequence).*//*────────If LIM is negative, a single result is shown for the abs(lim) entry.*/ parse arg lim .; if lim=='' then lim=99; aLim=abs(lim)w=length(aLim);$m.=.;   $m.0=0;$f.=.;   $f.0=1; Js=; Fs=; Ms= do j=0 to Alim Js=Js right(j,w); Fs=Fs right(F(j),w); Ms=Ms right(M(j),w) end /*j*/ if lim>0 then say 'Js=' Js; else say 'J('aLim")=" word(Js,aLim+1)if lim>0 then say 'Fs=' Fs; else say 'F('aLim")=" word(Fs,aLim+1)if lim>0 then say 'Ms=' Ms; else say 'M('aLim")=" word(Ms,aLim+1)exit /*stick a fork in it, we're all done. *//*───────────────────────────────────────────────────────────────────────────────────*/F: procedure expose$m. $f.; parse arg n; if$f.n==. then $f.n=n-M(F(n-1)); return$f.nM: procedure expose $m.$f.; parse arg n; if $m.n==. then$m.n=n-F(M(n-1)); return $m.n output when using the input of: -70000 J(70000)= 70000 F(70000)= 43262 M(70000)= 43262  output when using the input of a negative ¼ million: -250000 J(250000)= 250000 F(250000)= 154509 M(250000)= 154509  ## Ring  see "F sequence:"for i = 0 to 20 see "" + f(i) + " ";next see nlsee "M sequence:"for i = 0 to 20 see "" + m(i) + " "next func f n fr = 1 if n != 0 fr = n - m(f(n - 1)) ok return fr func m n mr = 0 if n != 0 mr = n - f(m(n - 1)) ok return mr  ## Ruby def F(n) n == 0 ? 1 : n - M(F(n-1))enddef M(n) n == 0 ? 0 : n - F(M(n-1))end p (Array.new(20) {|n| F(n) })p (Array.new(20) {|n| M(n) }) 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 ruby 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). ## Run BASIC print "F sequence:";for i = 0 to 20 print f(i);" ";next iprint :print "M sequence:";for i = 0 to 20 print m(i);" ";next iend function f(n) f = 1 if n <> 0 then f = n - m(f(n - 1))end function function m(n) m = 0 if n <> 0 then m = n - f(m(n - 1))end function Output: F sequence:1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 M sequence:0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12 ## Rust fn f(n: u32) -> u32 { match n { 0 => 1, _ => n - m(f(n - 1)) }} fn m(n: u32) -> u32 { match n { 0 => 0, _ => n - f(m(n - 1)) }} fn main() { for i in (0..20).map(f) { print!("{} ", i); } println!(""); for i in (0..20).map(m) { print!("{} ", i); } println!("")} 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 ## Sather class MAIN is f(n:INT):INT pre n >= 0 is if n = 0 then return 1; end; return n - m(f(n-1)); end; m(n:INT):INT pre n >= 0 is if n = 0 then return 0; end; return n - f(m(n-1)); end; main is loop i ::= 0.upto!(19); #OUT + #FMT("%2d ", f(i)); end; #OUT + "\n"; loop i ::= 0.upto!(19); #OUT + #FMT("%2d ", m(i)); end; end;end; There's no need to pre-declare F or M. ## Scala def F(n:Int):Int = if (n == 0) 1 else n - M(F(n-1))def M(n:Int):Int = if (n == 0) 0 else n - F(M(n-1)) println((0 until 20).map(F).mkString(", "))println((0 until 20).map(M).mkString(", ")) 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 ## Scheme define declarations are automatically mutually recursive: (define (F n) (if (= n 0) 1 (- n (M (F (- n 1)))))) (define (M n) (if (= n 0) 0 (- n (F (M (- n 1)))))) If you wanted to use a let-like construct to create local bindings, you would do the following. The define construct above is just a syntactic sugar for the following where the entire rest of the scope is used as the body. (letrec ((F (lambda (n) (if (= n 0) 1 (- n (M (F (- n 1))))))) (M (lambda (n) (if (= n 0) 0 (- n (F (M (- n 1)))))))) (F 19)) # evaluates to 12 The letrec indicates that the definitions can be recursive, and fact that we placed these two in the same letrec block makes them mutually recursive. ## Seed7 $ include "seed7_05.s7i"; const func integer: m (in integer: n) is forward; const func integer: f (in integer: n) is func  result    var integer: res is 0;  begin    if n = 0 then      res := 1;    else      res := n - m(f(n - 1));    end if;  end func; const func integer: m (in integer: n) is func  result    var integer: res is 0;  begin    if n = 0 then      res := 0;    else      res := n - f(m(n - 1));    end if;  end func; const proc: main is func  local    var integer: i is 0;  begin    for i range 0 to 19 do      write(f(i) lpad 3);    end for;    writeln;    for i range 0 to 19 do      write(m(i) lpad 3);    end for;    writeln;  end func;
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


## Sidef

func F(){};func M(){}; F = func(n) { n > 0 ? (n - M(F(n-1))) : 1 };M = func(n) { n > 0 ? (n - F(M(n-1))) : 0 }; [F, M].each { |seq|    (0..19).map {|i| seq.call(i)}.join(' ').say;}
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

## Smalltalk

Using block closure.

|F M ra rb| F := [ :n |  (n == 0)    ifTrue: [ 1 ]    ifFalse: [ n - (M value: (F value: (n-1))) ]       ]. M := [ :n |  (n == 0)    ifTrue: [ 0 ]    ifFalse: [ n - (F value: (M value: (n-1))) ]]. ra := OrderedCollection new.rb := OrderedCollection new.0 to: 19 do: [ :i |  ra add: (F value: i).  rb add: (M value: i)]. ra displayNl.rb displayNl.

## SNOBOL4

        define('f(n)') :(f_end)f       f = eq(n,0) 1 :s(return)        f = n - m(f(n - 1)) :(return)f_end         define('m(n)') :(m_end)m       m = eq(n,0) 0 :s(return)        m = n - f(m(n - 1)) :(return)m_end  *       # Test and displayL1      s1 = s1 m(i) ' ' ; s2 = s2 f(i) ' '        i = le(i,25) i + 1 :s(L1)        output = 'M: ' s1; output = 'F: ' s2end
Output:
M: 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12 13 14 14 15 16 16
F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 13 14 14 15 16 16

## SNUSP

The program shown calculates F(3) and demonstrates simple and mutual recursion.

       /======\F==!/=!\?\+#  | />-<-\    |    \@\-@/@\===?/<#    |      |    |$+++/======|====/ ! /=/ /+<<-\ | \!/======?\>>=?/<# dup | \<<+>+>-/ ! ! \======|====\ | | | | /===|==\ |M==!\=!\?\#| | | \@/-@/@/===?\<# ^ \>-<-/ | ^ ^ ^ ^ | | | | subtract from n | | | mutual recursion | | recursion | n-1 check for zero ## Standard ML fun f 0 = 1 | f n = n - m (f (n-1))and m 0 = 0 | m n = n - f (m (n-1)); The fun construct creates recursive functions, and the and allows a group of functions to call each other. The above is just a shortcut for the following: val rec f = fn 0 => 1 | n => n - m (f (n-1))and m = fn 0 => 0 | n => n - f (m (n-1)); which indicates that the functions call themselves (rec) and each other (and). ## Swift It just works. No special pre-declaration is necessary. func F(n: Int) -> Int { return n == 0 ? 1 : n - M(F(n-1))} func M(n: Int) -> Int { return n == 0 ? 0 : n - F(M(n-1))} for i in 0..20 { print("\(F(i)) ")}println()for i in 0..20 { print("\(M(i)) ")}println() ## Tcl proc m {n} { if {$n == 0 } { expr 0; } else {	expr {$n - [f [m [expr {$n-1}] ]]};    }}proc f {n} {    if { $n == 0 } { expr 1; } else { expr {$n - [m [f [expr {$n-1}] ]]}; }} for {set i 0} {$i < 20} {incr i} {    puts -nonewline [f $i]; puts -nonewline " ";}puts ""for {set i 0} {$i < 20} {incr i} {    puts -nonewline [m $i]; puts -nonewline " ";}puts "" ## TI-89 BASIC Define F(n) = when(n=0, 1, n - M(F(n - 1)))Define M(n) = when(n=0, 0, n - F(M(n - 1))) ## TXR (defun f (n) (if (>= 0 n) 1 (- n (m (f (- n 1)))))) (defun m (n) (if (>= 0 n) 0 (- n (f (m (- n 1)))))) (each ((n (range 0 15))) (format t "f(~s) = ~s; m(~s) = ~s\n" n (f n) n (m n))) $ txr mutual-recursion.txr
f(0) = 1; m(0) = 0
f(1) = 1; m(1) = 0
f(2) = 2; m(2) = 1
f(3) = 2; m(3) = 2
f(4) = 3; m(4) = 2
f(5) = 3; m(5) = 3
f(6) = 4; m(6) = 4
f(7) = 5; m(7) = 4
f(8) = 5; m(8) = 5
f(9) = 6; m(9) = 6
f(10) = 6; m(10) = 6
f(11) = 7; m(11) = 7
f(12) = 8; m(12) = 7
f(13) = 8; m(13) = 8
f(14) = 9; m(14) = 9
f(15) = 9; m(15) = 9

## uBasic/4tH

Translation of: BBC BASIC

uBasic/4tH supports mutual recursion. However, the underlying system can't support the stress this puts on the stack - at least not for the full sequence. This version uses memoization to alleviate the stress and speed up execution.

LOCAL(1)                               ' main uses locals as well FOR a@ = 0 TO 200                      ' set the array  @(a@) = -1NEXT PRINT "F sequence:"                    ' print the F-sequenceFOR a@ = 0 TO 20  PRINT FUNC(_f(a@));" ";NEXTPRINT PRINT "M sequence:"                    ' print the M-sequenceFOR a@ = 0 TO 20  PRINT FUNC(_m(a@));" ";NEXTPRINT END  _f PARAM(1)                            ' F-function  IF a@ = 0 THEN RETURN (1)            ' memoize the solution  IF @(a@) < 0 THEN @(a@) = a@ - FUNC(_m(FUNC(_f(a@ - 1))))RETURN (@(a@))                         ' return array element  _m PARAM(1)                            ' M-function  IF a@ = 0 THEN RETURN (0)            ' memoize the solution  IF @(a@+100) < 0 THEN @(a@+100) = a@ - FUNC(_f(FUNC(_m(a@ - 1))))RETURN (@(a@+100))                     ' return array element
Output:
F sequence:
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13
M sequence:
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12

0 OK, 0:199

## UNIX Shell

Works with: Bourne Again SHell
M(){    local n    n=$1 if [[$n -eq 0 ]]; then	echo -n 0    else	echo -n $(( n -$(F $(M$((n-1)) ) ) ))    fi} F(){    local n    n=$1 if [[$n -eq 0 ]]; then	echo -n 1    else	echo -n $(( n -$(M $(F$((n-1)) ) ) ))    fi} for((i=0; i < 20; i++)); do    F $i echo -n " "doneechofor((i=0; i < 20; i++)); do M$i    echo -n " "doneecho

## Ursala

Forward declarations are not an issue in Ursala, which allows any definition to depend on any symbol declared within the same scope. However, cyclic dependences are not accepted unless the programmer explicitly accounts for their semantics. If the recurrence can be solved using a fixed point combinator, the compiler can be directed to use one by the #fix directive as shown, in this case with one of a family of functional fixed point combinators from a library. (There are easier ways to define these functions in Ursala than by mutual recursion, but fixed points are useful for other things as well.)

#import std#import nat#import sol #fix general_function_fixer 0 F = ~&?\1! difference^/~& M+ F+ predecessorM = ~&?\0! difference^/~& F+ M+ predecessor

This test program applies both functions to the first twenty natural numbers.

#cast %nLW test = ^(F*,M*) iota 20
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>)

## x86 Assembly

Works with: nasm

Since all "labels" (symbols), if not local, can be seen by the whole code in the same source unit, we don't need special care to let the subroutine func_f call func_m. If the function would have been in another source unit, we should have declared it extern (the linker will resolve the symbol), as done for printf.
(It must be linked with the C standard library libc or similar and a startup code; lazyly a gcc mutrec.o works, being mutrec.o produced by e.g. nasm -f elf mutrec.asm)

	global	main	extern	printf 	section	.text func_f	mov	eax, [esp+4]	cmp	eax, 0	jz	f_ret	dec	eax	push	eax	call	func_f	mov	[esp+0], eax	call	func_m	add	esp, 4	mov	ebx, [esp+4]	sub	ebx, eax	mov	eax, ebx	retf_ret	mov	eax, 1	ret func_m	mov	eax, [esp+4]	cmp	eax, 0	jz	m_ret	dec	eax	push	eax	call	func_m	mov	[esp+0], eax	call	func_f	add	esp, 4	mov	ebx, [esp+4]	sub	ebx, eax	mov	eax, ebx	retm_ret	xor	eax, eax	ret main	mov	edx, func_f	call	output_res	mov	edx, func_m	call	output_res	ret output_res	xor	ecx, ecxloop0	push	ecx	call	edx         push    edx 	push	eax	push	form	call	printf	add	esp, 8 	pop     edx        pop     ecx 	inc	ecx	cmp	ecx, 20	jnz	loop0 	push	newline	call	printf	add	esp, 4 	ret  	section	.rodataform	db	'%d ',0newline	db	10,0 	end

## XPL0

code    ChOut=8, CrLf=9, IntOut=11; ffunc M; \forward-referenced function declaration func F(N);int N;return if N=0 then 1 else N - M(F(N-1)); func M(N);int N;return if N=0 then 0 else N - F(M(N-1)); int I;[for I:= 0 to 19 do [IntOut(0, F(I));  ChOut(0, ^ )];CrLf(0); for I:= 0 to 19 do [IntOut(0, M(I));  ChOut(0, ^ )];CrLf(0);]
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


## zkl

This works if the functions are in a file or on one line (in the REPL) as zkl doesn't like referencing undefined objects. You could also pass/close the other function.

fcn f(n){ if(n==0)return(1); n-m(f(n-1,m),f) }fcn m(n){ if(n==0)return(0); n-f(m(n-1,f),m) }[0..19].apply(f).println();  // or foreach n in ([0..19]){ print(f(n)," ") }[0..19].apply(m).println();  // or foreach n in ([0..19]){ print(m(n)," ") }
Output:
L(1,1,2,2,3,3,4,5,5,6,6,7,8,8,9,9,10,11,11,12)
L(0,0,1,2,2,3,4,4,5,6,6,7,7,8,9,9,10,11,11,12)