⚠️ Warning: This is a draft ⚠️

This means it might contain formatting issues, incorrect code, conceptual problems, or other severe issues.

If you want to help to improve and eventually enable this page, please fork RosettaGit's repository and open a merge request on GitHub.

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 [[wp:Hofstadter sequence#Hofstadter Female and Male sequences|Hofstadter Female and Male sequences]] defined as: :\begin\left\{align\right\} F\left(0\right)&=1\ ;\ M\left(0\right)=0 \ F\left(n\right)&=n-M\left(F\left(n-1\right)\right), \quad n>0 \ M\left(n\right)&=n-F\left(M\left(n-1\right)\right), \quad n>0. \end\left\{align\right\}

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

ABAP

This works for ABAP Version 7.40 and can be implemented in procedural ABAP as well, but with classes it is much more readable. As this allows a method with a returning value to be an input for a subsequent method call.


report z_mutual_recursion.

public section.
class-methods:
f
importing
n             type int4
returning
value(result) type int4,

m
importing
n             type int4
returning
value(result) type int4.
endclass.

method f.
result = cond int4(
when n eq 0
then 1
else n - m( f( n - 1 ) ) ).
endmethod.

method m.
result = cond int4(
when n eq 0
then 0
else n - f( m( n - 1 ) ) ).
endmethod.
endclass.

start-of-selection.
write: |{ reduce string(
init results = |f(0 - 19): { hoffstadter_sequences=>f( 0 ) }|
for i = 1 while i < 20
next results = |{ results }, { hoffstadter_sequences=>f( i ) }| ) }|, /.

write: |{ reduce string(
init results = |m(0 - 19): { hoffstadter_sequences=>m( 0 ) }|
for i = 1 while i < 20
next results = |{ results }, { hoffstadter_sequences=>m( i ) }| ) }|, /.



{{output}}


f(0 - 19): 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12

m(0 - 19): 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12



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

{{trans|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

{{trans|C}}

{{works with|ALGOL 68|Standard - no extensions to language used}} {{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}} {{works with|ELLA ALGOL 68|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)
)


{{out}}


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.


AppleScript

-- f :: Int -> Int
on f(x)
if x = 0 then
1
else
x - m(f(x - 1))
end if
end f

-- m :: Int -> Int
on m(x)
if x = 0 then
0
else
x - f(m(x - 1))
end if
end m

-- TEST
on run
set xs to range(0, 19)

{map(f, xs), map(m, xs)}
end run

-- GENERIC FUNCTIONS

-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
tell mReturn(f)
set lng to length of xs
set lst to {}
repeat with i from 1 to lng
set end of lst to lambda(item i of xs, i, xs)
end repeat
return lst
end tell
end map

-- Lift 2nd class handler function into 1st class script wrapper
-- mReturn :: Handler -> Script
on mReturn(f)
if class of f is script then
f
else
script
property lambda : f
end script
end if
end mReturn

-- range :: Int -> Int -> [Int]
on range(m, n)
if n < m then
set d to -1
else
set d to 1
end if
set lst to {}
repeat with i from m to n by d
set end of lst to i
end repeat
return lst
end range


{{Out}}

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


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
}


{{trans|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.

cat mutual_recursion.awk:
#!/usr/local/bin/gawk -f

# User defined functions
function F(n)
{ return n == 0 ? 1 : n - M(F(n-1)) }

function M(n)
{ return n == 0 ? 0 : 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 ""
}


{{out}}


$awk -f mutual_recursion.awk 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  BaCon ' Mutually recursive FUNCTION F(int n) TYPE int RETURN IIF(n = 0, 1, n - M(F(n -1))) END FUNCTION FUNCTION M(int n) TYPE int RETURN IIF(n = 0, 0, n - F(M(n - 1))) END FUNCTION ' Get iteration limit, default 20 SPLIT ARGUMENT$ BY " " TO arg$SIZE args limit = IIF(args > 1, VAL(arg$[1]), 20)

FOR i = 0 TO limit
PRINT F(i) FORMAT "%2d "
NEXT
PRINT
FOR i = 0 TO limit
PRINT M(i) FORMAT "%2d "
NEXT
PRINT


{{out}}

prompt$./mutually-recursive 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  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 IF END FUNCTION FUNCTION m! (n!) IF n = 0 THEN m = 0 ELSE m = f(m(n - 1)) END IF END 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))  {{out}}  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  ==={{header|IS-BASIC}}=== 100 PROGRAM "Hofstad.bas" 110 PRINT "F sequence:" 120 FOR I=0 TO 20 130 PRINT F(I); 140 NEXT 150 PRINT :PRINT "M sequence:" 160 FOR I=0 TO 20 170 PRINT M(I); 180 NEXT 190 DEF F(N) 200 IF N=0 THEN 210 LET F=1 220 ELSE 230 LET F=N-M(F(N-1)) 240 END IF 250 END DEF 260 DEF M(N) 270 IF N=0 THEN 280 LET M=0 290 ELSE 300 LET M=N-F(M(N-1)) 310 END IF 320 END DEF  ## Bc bc cat mutual_recursion.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"; quit  {{out}}  GNU bc mutual_recursion.bc bc 1.06.95 Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc. This is free software with ABSOLUTELY NO WARRANTY. For details type warranty'. 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  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 [[Mutual Recursion#C|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)); }  {{out}}  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 F console.log [0...20].map M  {{out}} 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 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; }  {{out}} [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]  =={{header|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 )  {{out}} 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");
f; t;!"
"m; t;!


Fantom


class Main
{
static Int f (Int n)
{
if (n <= 0) // ensure n > 0
return 1
else
return n - m(f(n-1))
}

static Int m (Int n)
{
if (n <= 0) // ensure n > 0
return 0
else
return n - f(m(n-1))
}

public static Void main ()
{
50.times |Int n| { echo (f(n)) }
}
}



In [http://wiki.formulae.org/Mutual_recursion this] page you can see the solution of this task.

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text ([http://wiki.formulae.org/Editing_F%C5%8Drmul%C3%A6_expressions more info]). Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for transportation effects more than visualization and edition.

The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.

Forth

Forward references required for mutual recursion may be set up using DEFER.

defer m

: f ( n -- n )
dup 0= if 1+ exit then
dup 1- recurse m - ;

:noname ( n -- n )
dup 0= if exit then
dup 1- recurse f - ;
is m

: test ( xt n -- ) cr 0 do i over execute . loop drop ;

' m defer@ 20 test \ 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12
' f 20 test        \ 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12


Fortran

As long 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|95 and later}}

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


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

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


FreeBASIC

' FB 1.05.0 Win64

' Need forward declaration of M as it's used
' by F before its defined
Declare Function M(n As Integer) As Integer

Function F(n As Integer) As Integer
If n = 0 Then
Return 1
End If
Return n - M(F(n - 1))
End Function

Function M(n As Integer) As Integer
If n = 0 Then
Return 0
End If
Return n - F(M(n - 1))
End Function

Dim As Integer n = 24
Print "n :";
For i As Integer = 0 to n : Print Using "###"; i;    : Next
Print
Print String(78, "-")
Print "F :";
For i As Integer = 0 To n : Print Using "###"; F(i); : Next
Print
Print "M :";
For i As Integer = 0 To n : Print Using "###"; M(i); : Next
Print
Print "Press any key to quit"
Sleep


{{out}}


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



Go

It just works. No special pre-declaration is necessary.

package main
import "fmt"

func F(n int) int {
if n == 0 { return 1 }
return n - M(F(n-1))
}

func M(n int) int {
if n == 0 { return 0 }
return n - F(M(n-1))
}

func main() {
for i := 0; i < 20; i++ {
fmt.Printf("%2d ", F(i))
}
fmt.Println()
for i := 0; i < 20; i++ {
fmt.Printf("%2d ", M(i))
}
fmt.Println()
}


Groovy

Solution:

def f, m  // recursive closures must be declared before they are defined
f = { n -> n == 0 ? 1 : n - m(f(n-1)) }
m = { n -> n == 0 ? 0 : n - f(m(n-1)) }


Test program:

println 'f(0..20): ' + (0..20).collect { f(it) }
println 'm(0..20): ' + (0..20).collect { m(it) }


{{out}}

f(0..20): [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13]
m(0..20): [0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12]


Haskell's definitions constructs (at the top level, or inside a let or where construct) are always mutually-recursive:

f 0 = 1
f n | n > 0 = n - m (f $n-1) m 0 = 0 m n | n > 0 = n - f (m$ n-1)

main = do
print $map f [0..19] print$ map m [0..19]


procedure main(arglist)
every write(F(!arglist))   # F of all arguments
end

procedure F(n)
if integer(n) >= 0 then
return (n = 0, 1) |  n - M(F(n-1))
end

procedure M(n)
if integer(n) >= 0 then
return (0 = n) | n - F(M(n-1))
end


Idris

mutual {
F : Nat -> Nat
F Z = (S Z)
F (S n) = (S n) minus M(F(n))

M : Nat -> Nat
M Z = Z
M (S n) = (S n) minus F(M(n))
}


Io

f := method(n, if( n == 0, 1, n - m(f(n-1))))
m := method(n, if( n == 0, 0, n - f(m(n-1))))

Range
0 to(19) map(n,f(n)) println
0 to(19) map(n,m(n)) println


{{out}}

list(1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12)
list(0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12)


J

F =: 1:(-  M @ $: @ <:) @.* M."0 M =: 0:(- F @$: @ <:) @.* M."0


Example use:

   F i. 20
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12


That said, note that numbers are defined recursively, so other some approaches using numbers which give equivalent results should be acceptable.

Java

{{trans|C}}

public static int f(final int n)
{
return n == 0 ? 1 : n - m(f(n - 1));
}

public static int m(final int n)
{
return n == 0 ? 0 : n - f(m(n - 1));
}

public static void main(final 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));
}


JavaScript

function f(num) {
return (num === 0) ? 1 : num - m(f(num - 1));
}

function m(num) {
return (num === 0) ? 0 : num - f(m(num - 1));
}

function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(
function (x, i) { return m + i; }
);
}

var a = range(0, 19);

//return a new array of the results and join with commas to print
console.log(a.map(function (n) { return f(n); }).join(', '));
console.log(a.map(function (n) { return m(n); }).join(', '));


{{out}}

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


ES6 implementation

 (num === 0) ? 1 : num - m(f(num - 1));
var m = num => (num === 0) ? 0 : num - f(m(num - 1));

function range(m, n) {
return Array.apply(null, Array(n - m + 1)).map(
function (x, i) { return m + i; }
);
}

var a = range(0, 19);

//return a new array of the results and join with commas to print
console.log(a.map(n => f(n)).join(', '));
console.log(a.map(n => m(n)).join(', '));


More ES6 implementation

var range = (m, n) => Array(... Array(n - m + 1)).map((x, i) => m + i)


jq

jq supports mutual recursion but requires functions to be defined before they are used. In the present case, this can be accomplished by defining an inner function.

He we define F and M as arity-0 filters:


def M:
def F: if . == 0 then 1 else . - ((. - 1) | F | M) end;
if . == 0 then 0 else . - ((. - 1) | M | F) end;

def F:
if . == 0 then 1 else . - ((. - 1) | F | M) end;


Example:


[range(0;20) | F],
[range(0;20) | M]

$jq -n -c -f Mutual_recursion.jq [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]  Jsish /* Mutual recursion, is jsish */ function f(num):number { return (num === 0) ? 1 : num - m(f(num - 1)); } function m(num):number { return (num === 0) ? 0 : num - f(m(num - 1)); } function range(n=10, start=0, step=1):array { var a = Array(n).fill(0); for (var i in a) a[i] = start+i*step; return a; } var a = range(21); puts(a.map(function (n) { return f(n); }).join(', ')); puts(a.map(function (n) { return m(n); }).join(', ')); /* =!EXPECTSTART!= 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 =!EXPECTEND!= */  {{out}} prompt$ jsish -u mutual-recursion.jsi
[PASS] mutual-recursion.jsi

prompt$jsish mutual-recursion.jsi 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  Julia F(n) = n < 1 ? one(n) : n - M(F(n - 1)) M(n) = n < 1 ? zero(n) : n - F(M(n - 1))  {{out}}  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])  Kotlin // version 1.0.6 fun f(n: Int): Int = when { n == 0 -> 1 else -> n - m(f(n - 1)) } fun m(n: Int): Int = when { n == 0 -> 0 else -> n - f(m(n - 1)) } fun main(args: Array<String>) { val n = 24 print("n :") for (i in 0..n) print("%3d".format(i)) println() println("-".repeat(78)) print("F :") for (i in 0..24) print("%3d".format(f(i))) println() print("M :") for (i in 0..24) print("%3d".format(m(i))) println() }  {{out}}  n : 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 ------------------------------------------------------------------------------ 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 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  Liberty BASIC  print "F sequence." for i = 0 to 20 print f(i);" "; next print print "M sequence." for i = 0 to 20 print 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  {{out}} 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 functions sub setfont(strfont) ThisComponent.getCurrentController.getViewCursor.charFontName = strfont end 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) newline end 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 = nstr end function '// Hofstadter Female-Male function definitions function 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 routine sub 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 20 F(n) = 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 M(n) = 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12  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-1 end to f :n if 0 = :n [output 1] output :n - m f :n-1 end 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, [" "], []))); } }  {{out}} 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 end function 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,n function m(n) return n > 0 and n - f(m(n-1)) or 0 end function f(n) return n > 0 and n - m(f(n-1)) or 1 end  M2000 Interpreter A function can call a global function and must be global to call it again by the second function A group's function can call sibling function from same group. We can use This.F() or simply .f() to use group's f() member. We can use subroutines, which can call each other, in a module, and we can use the modules stack of values to get results from subs. Subs running as parts of module, and see same variables and same stack of values. Arguments are local to sub, and we can define local variables too. Last module export to clipboard and that used for output here.  \\ set console 70 characters by 40 lines Form 70, 40 Module CheckSubs { Flush Document one$, two$For i =0 to 20 Print format$("{0::-3}",i);
f(i)
\\  number pop then top value of stack
one$=format$("{0::-3}",number)
m(i)
two$=format$("{0::-3}",number)
Next i
Print
Print one$Print two$
Sub f(x)
if x<=0 then Push 1 : Exit sub
f(x-1)  ' leave result to for m(x)
m()
push x-number
End Sub
Sub m(x)
if x<=0 then Push 0 : Exit sub
m(x-1)
f()
push x-number
End Sub
}
CheckSubs

Module Checkit {
Function global f(n) {
if n=0 then =1: exit
if n>0 then  =n-m(f(n-1))
}
Function global m(n) {
if n=0 then =0
if n>0 then  =n-f(m(n-1))

}
Document one$, two$
For i =0 to 20
Print format$("{0::-3}",i); one$=format$("{0::-3}",f(i)) two$=format$("{0::-3}",m(i)) Next i Print Print one$
Print two$} Checkit Module Checkit2 { Group Alfa { function f(n) { if n=0 then =1: exit if n>0 then =n-.m(.f(n-1)) } function m(n) { if n=0 then =0 if n>0 then =n-.f(.m(n-1)) } } Document one$, two$For i =0 to 20 Print format$("{0::-3}",i);
one$=format$("{0::-3}",Alfa.f(i))
two$=format$("{0::-3}",Alfa.m(i))
Next i
Print
Print one$Print two$
Clipboard one$+{ }+two$
}
Checkit2



{{out}}


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



M4

define(female',ifelse(0,$1,1,eval($1 - male(female(decr($1))))')')dnl define(male',ifelse(0,$1,0,eval($1 - female(male(decr($1))))')')dnl
define(loop',ifelse($1,$2,,$3($1) loop(incr($1),$2,$3')')')dnl loop(0,20,female') loop(0,20,male')  Maple female_seq := proc(n) if (n = 0) then return 1; else return n - male_seq(female_seq(n-1)); end if; end proc; male_seq := proc(n) if (n = 0) then return 0; else return n - female_seq(male_seq(n-1)); end if; end proc; seq(female_seq(i), i=0..10); seq(male_seq(i), i=0..10);  {{Out|Output}} 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6  Mathematica Without caching: f[0]:=1 m[0]:=0 f[n_]:=n-m[f[n-1]] m[n_]:=n-f[m[n-1]]  With caching: f[0]:=1 m[0]:=0 f[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  {{out}}  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 mmix LOC Data_Segment GREG @ NL BYTE #a,0 GREG @ buf OCTA 0,0 t IS$128
Ja	IS	$127 LOC #1000 GREG @ // print 2 digits integer with trailing space to StdOut // reg$3 contains int to be printed
bp	IS	$71 0H GREG #0000000000203020 prtInt STO 0B,buf % initialize buffer LDA bp,buf+7 % points after LSD % REPEAT 1H 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 function F 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 1 1H 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 function M GET$1,rJ
PBNZ	$0,1F PUT rJ,$1
POP	1,0		% return M 0 = 0
1H	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 run Main 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  {{out}} ~/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)  =={{header|Objective-C}}== Objective-C has prior declaration rules similar to those stated above for [[Mutual Recursion#C|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.  @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 {{trans|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 endfor endfunction 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 endfor endfunction  # testing ra = 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 - ; 0 20 seqFrom map(#F) println 0 20 seqFrom map(#M) println  {{out}}  [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]  Ol 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.  (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)))))))) (print (F 19))) ; produces 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))))))) //Test ORDER_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 end in {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";
}


{{out}}


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 $F$ and $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;


{{out}}


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

You should normally explicitly declare forward routines (strictly necessary only when using optional or named parameters), since it often makes things easier to understand. There would be no point pre-declaring F, since it is not called before it is defined anyway.

forward function M(integer n)

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 for
printf(1,"\n")
for i=0 to 20 do
printf(1," %d",M(i))
end for


{{out}}


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

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

$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 def n 0 eq {1} { n n 1 sub female male sub }ifelse }def /male{ /n exch def n 0 eq {0} { n n 1 sub male female sub }ifelse }def  {{libheader|initlib}} postscript /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 i If 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  {{out}} 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|3.0}}. {{works with|Python|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) ])  {{out}} [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" 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]  {{out}} 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 the Hofstadter Male and Female sequences). */ 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 the Hofstadter Male and Female sequences). */ 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.n
M: 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 the Hofstadter Male and Female sequences). */ /*───────────────── 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.n
M: 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 nl see "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)) end def 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) })  {{out}} [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 i print :print "M sequence:"; for i = 0 to 20 print m(i);" "; next i end 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  {{out}} 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!("") }  {{out}} 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  =={{header|S-lang}}== % Forward definitions: [also deletes any existing definition] define f(); define m(); define f(n) { if (n == 0) return 1; else if (n < 0) error("oops"); return n - m(f(n - 1)); } define m(n) { if (n == 0) return 0; else if (n < 0) error("oops"); return n - f(m(n - 1)); } foreach$1 ([0:19]) () = printf("%d ", f($1)); () = printf("\n"); foreach$1 ([0:19]) () = printf("%d ", m($1)); () = printf("\n");  {{out}} txt 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(", "))  {{out}} 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
end for;
writeln;
for i range 0 to 19 do
end for;
writeln;
end func;


{{out}}


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|
{|i| seq.call(i)}.map(^20).join(' ').say
}


{{out}}

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 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 display
L1      s1 = s1 m(i) ' ' ; s2 = s2 f(i) ' '
i = le(i,25) i + 1 :s(L1)
output = 'M: ' s1; output = 'F: ' s2
end


{{out}}

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  SPL f(n)= ? n=0, <= 1 <= n-m(f(n-1)) . m(n)= ? n=0, <= 0 <= n-f(m(n-1)) . > i, 0..20 fs += " "+f(i) ms += " "+m(i) < #.output("F:",fs) #.output("M:",ms)  {{out}}  F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 M: 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12  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:  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 ""  =={{header|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

{{trans|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 [https://en.wikipedia.org/wiki/Memoization 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@) = -1 NEXT

PRINT "F sequence:" ' print the F-sequence FOR a@ = 0 TO 20 PRINT FUNC(_f(a@));" "; NEXT PRINT

PRINT "M sequence:" ' print the M-sequence FOR a@ = 0 TO 20 PRINT FUNC(_m(a@));" "; NEXT PRINT

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


{{out}}

txt
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 " " done echo for((i=0; i < 20; i++)); do M$i
echo -n " "
done
echo


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+ predecessor
M = ~&?\0! difference^/~& F+ M+ predecessor


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

#cast %nLW

test = ^(F*,M*) iota 20


{{out}}


(
<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>)


VBA

Private Function F(ByVal n As Integer) As Integer
If n = 0 Then
F = 1
Else
F = n - M(F(n - 1))
End If
End Function

Private Function M(ByVal n As Integer) As Integer
If n = 0 Then
M = 0
Else
M = n - F(M(n - 1))
End If
End Function

Public Sub MR()
Dim i As Integer
For i = 0 To 20
Debug.Print F(i);
Next i
Debug.Print
For i = 0 To 20
Debug.Print M(i);
Next i
End Sub


{{out}}

 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


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
mov	ebx, [esp+4]
sub	ebx, eax
mov	eax, ebx
ret
f_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
mov	ebx, [esp+4]
sub	ebx, eax
mov	eax, ebx
ret
m_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, ecx
loop0
push	ecx
call	edx

push    edx

push	eax
push	form
call	printf

pop     edx
pop     ecx

inc	ecx
cmp	ecx, 20
jnz	loop0

push	newline
call	printf

ret

section	.rodata
form
db	'%d ',0
newline
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);
]


{{out}}


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



Yabasic

{{trans|AWK}}

// User defined functions
sub F(n)
if n = 0 return 1
return n - M(F(n-1))
end sub

sub M(n)
if n = 0 return 0
return n - F(M(n-1))
end sub

for i = 0 to 20
print F(i) using "###";
next
print
for i = 0 to 20
print M(i) using "###";
next
print


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)," ") }


{{out}}


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)