I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# Mutual recursion

(Redirected from 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).

## 8080 Assembly

The 8080 processor has built-in support for recursion, at the instruction level. The processor keeps a stack pointer, called SP, which is a 16-bit register that can be set by the program to point anywhere in the address space. The stack pointer points to the topmost word on the stack. The stack grows downward into memory: when a word is pushed onto the stack, the SP is decremented by 2, and the word written at the new location. When a word is popped from the stack, it is read from the location the SP is pointing to, and afterwards the SP is incremented by 2.

The instruction set includes a call instruction, which pushes the location of the next instruction onto the stack, and then jumps to the given location. Its counterpart is the ret instruction, which pops a location from the stack and jumps there. There are also push and pop instructions, to push and pop the values of register pairs on and off the stack directly. This can be used, among other things, to save 'local variables' in a recursive routine, as the code below does.

	org	100h	jmp	test	;;; Implementation of F(A).F:	ana	a	; Zero?	jz	one	; Then set A=1	mov	b,a	; Otherwise, set B=A,	push	b	; And put it on the stack	dcr	a	; Set A=A-1	call	F	; Set A=F(A-1)	call	M 	; Set A=M(F(A-1))	pop	b	; Retrieve input value	cma		; (-A)+B is actually one cycle faster	inr	a	; than C=A;A=B;A-=B, and equivalent	add	b	retone:	mvi	a,1	; Set A to 1,	ret		; and return.	;;; Implementation of M(A).M:	ana	a	; Zero?	rz		; Then keep it that way and return.	mov	b,a	push	b	; Otherwise, same deal as in F,	dcr	a	; but M and F are called in opposite	call	M 	; order.	call	F	pop	b	cma	inr	a	add	b	ret	;;; Demonstration code.test:	lhld	6	; Set stack pointer to highest usable	sphl		; memory.	;;; Print F([0..15])	lxi	d,fpfx	; Print "F: " 	mvi 	c,9		call	5	xra	a	; Start with N=0floop:	push	psw	; Keep N	call	F	; Get value for F(N)	call	pdgt	; Print it	pop	psw	; Restore N	inr 	a	; Next N	cpi	16	; Done yet?	jnz	floop	;;; Print M([0..15])	lxi	d,mpfx	; Print "\r\nM: "	mvi	c,9	call	5	xra	a	; Start with N=0mloop:	push	psw	; same deal as above	call	M	call	pdgt	pop	psw	; Restore N	inr	a	cpi	16	jnz	mloop	rst	0	; Explicit exit, we got rid of system stack	;;; Print digit and spacepdgt:	adi	'0'	; ASCII	mov	e,a	mvi	c,2	call	5	mvi	e,' '	; Space	mvi	c,2	jmp	5	; Tail call optimizationfpfx:	db	'F: $'mpfx: db 13,10,'M:$'
Output:
F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9
M: 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9

## 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. class hoffstadter_sequences definition.  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.  class hoffstadter_sequences implementation.  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

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.

## APL

Works with: Dyalog APL
f ← {⍵=0:1 ⋄ ⍵-m∇⍵-1}m ← {⍵=0:0 ⋄ ⍵-f∇⍵-1}⍉'nFM'⍪↑(⊢,f,m)¨0,⍳20
Output:
n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
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

## AppleScript

-- f :: Int -> Inton f(x)    if x = 0 then        1    else        x - m(f(x - 1))    end ifend f -- m :: Int -> Inton m(x)    if x = 0 then        0    else        x - f(m(x - 1))    end ifend m  -- TESTon 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 tellend map -- Lift 2nd class handler function into 1st class script wrapper -- mReturn :: Handler -> Scripton mReturn(f)    if class of f is script then        f    else        script            property lambda : f        end script    end ifend 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 lstend range
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}}

## ARM Assembly

Unlike on the x86 family of processors, the ARM instruction set does not include specialized call and ret instructions. However, the program counter is a visible register (r15, also called pc), so it can be loaded and saved as any other. Nor is there a specialized stack pointer, though the load and store instructions offer pre- and postincrement as well as pre- and postdecrement on the register used as a pointer, making any register usable as a stack pointer.

By convention, r13 is used as the system stack pointer and is therefore also called sp, and r14 is used to store the return address for a function, and is therefore also called the *link register* or lr. The assembler recognizes push {x} and pop {x} instructions, though these are really pseudoinstructions, that generate the exact same machine code as ldmia r13!,{x} and stmdb r13!,{x}, these being, respectively, load with postincrement and store with predecrement on r13.

The link register is slightly special in that there is a family of branch-and-link instructions (bl). These are the same as mov r14,pc ; mov/ldr pc,<destination>, but in one machine instruction instead of two. This is the general way of calling subroutines, meaning no stack access is necessary unless the subroutine wants to call others in turn, in which case the link register must be saved by hand (as the code below shows several ways of doing).

.text.global _start	@@@	Implementation of F(n), n in R0. n is considered unsigned.F:	tst	r0,r0		@ n = 0?	moveq	r0,#1		@ In that case, the result is 1	bxeq	lr		@ And we can return to the caller	push	{r0,lr}		@ Save link register and argument to stack	sub	r0,r0,#1	@ r0 -= 1    = n-1	bl	F		@ r0 = F(r0) = F(n-1)	bl	M		@ r0 = M(r0) = M(F(n-1))	pop	{r1,lr}		@ Restore link register and argument in r1	sub	r0,r1,r0	@ Result is n-F(M(n-1))	bx	lr		@ Return to caller. 	@@@	Implementation of M(n), n in R0. n is considered unsigned.M:	tst	r0,r0		@ n = 0?	bxeq	lr		@ In that case the result is also 0; return.	push	{r0,lr}		@ Save link register and argument to stack	sub	r0,r0,#1	@ r0 -= 1    = n-1	bl	M		@ r0 = M(r0) = M(n-1)	bl	F		@ r0 = M(r0) = F(M(n-1))	pop	{r1,lr}		@ Restore link register and argument in r1	sub	r0,r1,r0	@ Result is n-M(F(n-1))	bx	lr		@ Return to caller 	@@@	Print F(0..15) and M(0..15)_start:	ldr	r1,=fmsg	@ Print values for F	ldr	r4,=F	bl	prfn	ldr	r1,=mmsg	@ Print values for M	ldr	r4,=M	bl	prfn	mov	r7,#1		@ Exit process	swi	#0 	@@@	Helper function for output: print [r1], then [r4](0..15)	@@@	This assumes [r4] preserves r3 and r4; M and F do.prfn:	push	{lr}		@ Keep link register	bl	pstr		@ Print the string	mov	r3,#0		@ Start at 01:	mov	r0,r3		@ Call the function in r4 with current number		blx	r4	add	r0,r0,#'0	@ Make ASCII digit	ldr	r1,=dgt		@ Store in digit string	strb	r0,[r1]	ldr	r1,=dstr	@ Print result	bl	pstr	add	r3,r3,#1	@ Next number	cmp	r3,#15		@ Keep going up to and including 15	bls	1b	ldr	r1,=nl		@ Print newline afterwards	bl	pstr	pop	{pc}		@ Return to address on stack	@@@	Print length-prefixed string r1 to stdoutpstr:	push	{lr}		@ Keep link register	mov	r0,#1		@ stdout = 1	ldrb	r2,[r1],#1	@ r2 = length prefix	mov	r7,#4		@ 4 = write syscall	swi	#0	pop	{pc}		@ Return to address on stack.datafmsg:	.ascii	"\3F: "mmsg:	.ascii	"\3M: "dstr:	.ascii	"\2"dgt:	.ascii	"* "nl:	.ascii 	"\1\n"
Output:
F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9
M: 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9

## Arturo

f: $[n][ if? n=0 -> 1 else -> n-m f n-1 ]m:$[n][ if? n=0 -> 0 else -> n-f m n-1 ] loop 0..20 'i [	print ["f(" i ")=" f i]	print ["m(" i ")=" m i]	print ""]
Output:
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

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

cat mutual_recursion.awk:#!/usr/local/bin/gawk -f # User defined functionsfunction 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 ""}
Output:
Output:

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

## FOCAL

01.01 C--PRINT F(0..15) AND M(0..15)01.10 T "F(0..15)"01.20 F X=0,15;S N=X;D 4;T %1,N01.30 T !"M(0..15)"01.40 F X=0,15;S N=X;D 5;T %1,N01.50 T !01.60 Q 04.01 C--N = F(N)04.10 I (N(D)),4.11,4.204.11 S N(D)=1;R04.20 S D=D+1;S N(D)=N(D-1)-1;D 4;D 504.30 S D=D-1;S N(D)=N(D)-N(D+1) 05.01 C--N = M(N)05.10 I (N(D)),5.11,5.205.11 R05.20 S D=D+1;S N(D)=N(D-1)-1;D 5;D 405.30 S D=D-1;S N(D)=N(D)-N(D+1)
Output:
F(0..15)= 1= 1= 2= 2= 3= 3= 4= 5= 5= 6= 6= 7= 8= 8= 9= 9
M(0..15)= 0= 0= 1= 2= 2= 3= 4= 4= 5= 6= 6= 7= 7= 8= 9= 9

## 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 [email protected] 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 version 95 and later
module MutualRec  implicit nonecontains  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 definedDeclare 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 = 24Print "n :";For i As Integer = 0 to n : Print Using "###"; i;    : NextPrint Print String(78, "-")Print "F :";For i As Integer = 0 To n : Print Using "###"; F(i); : NextPrintPrint "M :";For i As Integer = 0 To n : Print Using "###"; M(i); : NextPrintPrint "Press any key to quit"Sleep
Output:
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


## Fōrmulæ

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. 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 storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.

## Go

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

package mainimport "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 definedf = { 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) }
Output:
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 = 1f 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]

## Icon and Unicon

procedure main(arglist)every write(F(!arglist))   # F of all argumentsend 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)))) Range0 to(19) map(n,f(n)) println0 to(19) map(n,m(n)) println
Output:
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."0M =: 0:(- F @$: @ <:) @.* M."0

Example use:

   F i. 201 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

Replace translation (that doesn't compile) with a Java native implementation.

 import java.util.HashMap;import java.util.Map; public class MutualRecursion {     public static void main(final String args[]) {        int max = 20;        System.out.printf("First %d values of the Female sequence:  %n", max);        for (int i = 0; i < max; i++) {            System.out.printf("  f(%d) = %d%n", i, f(i));        }        System.out.printf("First %d values of the Male sequence:  %n", max);        for (int i = 0; i < 20; i++) {            System.out.printf("  m(%d) = %d%n", i, m(i));        }    }     private static Map<Integer,Integer> F_MAP = new HashMap<>();     private static int f(final int n) {        if ( F_MAP.containsKey(n) ) {            return F_MAP.get(n);        }        int fn = n == 0 ? 1 : n - m(f(n - 1));        F_MAP.put(n, fn);        return fn;    }     private static Map<Integer,Integer> M_MAP = new HashMap<>();     private static int m(final int n) {        if ( M_MAP.containsKey(n) ) {            return M_MAP.get(n);        }        int mn = n == 0 ? 0 : n - f(m(n - 1));        M_MAP.put(n, mn);        return mn;    }  } 
Output:

First 20 values of the Female sequence:

 f(0) = 1
f(1) = 1
f(2) = 2
f(3) = 2
f(4) = 3
f(5) = 3
f(6) = 4
f(7) = 5
f(8) = 5
f(9) = 6
f(10) = 6
f(11) = 7
f(12) = 8
f(13) = 8
f(14) = 9
f(15) = 9
f(16) = 10
f(17) = 11
f(18) = 11
f(19) = 12


First 20 values of the Male sequence:

 m(0) = 0
m(1) = 0
m(2) = 1
m(3) = 2
m(4) = 2
m(5) = 3
m(6) = 4
m(7) = 4
m(8) = 5
m(9) = 6
m(10) = 6
m(11) = 7
m(12) = 7
m(13) = 8
m(14) = 9
m(15) = 9
m(16) = 10
m(17) = 11
m(18) = 11
m(19) = 12


## 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 printconsole.log(a.map(function (n) { return f(n); }).join(', '));console.log(a.map(function (n) { return m(n); }).join(', '));
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

ES6 implementation

var f = num => (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 printconsole.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, 130, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12=!EXPECTEND!=*/ Output: 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)) 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])  ## 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()} Output: 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  ## Lambdatalk  {def F {lambda {:n} {if {= :n 0} then 1 else {- :n {M {F {- :n 1}}}} }}}{def M {lambda {:n} {if {= :n 0} then 0 else {- :n {F {M {- :n 1}}}} }}} {map F {serie 0 19}}-> 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12{map M {serie 0 19}}-> 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12  The naïve version is very slow, {F 80} requires 3800 ms on a recent laptop, so let's memoize:  {def cache {def cache.F {#.new}} {def cache.M {#.new}} {lambda {:f :n} {let { {:f :f} {:n :n} {:cx {if {equal? :f MF} then {cache.F} else {cache.M}}} } {if {equal? {#.get :cx :n} undefined} then {#.get {#.set! :cx :n {:f :n}} :n} else {#.get :cx :n}}}}}-> cache {def MF {lambda {:n} {if {= :n 0} then 1 else {- :n {MM {cache MF {- :n 1}}}}}}}-> MF {def MM {lambda {:n} {if {= :n 0} then 0 else {- :n {MF {cache MM {- :n 1}}}}}}}-> MM {MF 80}-> 50 (requires 55 ms) {map MF {serie 0 100}} (requires75ms)-> 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 62  ## 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 ## 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 linesForm 70, 40Module 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$}CheckitModule 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  
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


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') ## MAD By default, functions in MAD are not reentrant. There is also no variable scope, all variables are always global. Functions can call other functions, but on the old IBM mainframes this was done by storing the return address in a special location (one per function); should a function call itself (either directly or indirectly), the return address would be overwritten. MAD does include a stack mechanism, but it is entirely manual. The programmer must allocate memory for it himself and activate it by hand, by default there is no stack. The command for this is SET LIST TO array. Once this is done, however, variables can be pushed and popped (using the SAVE and RESTORE commands). Furthermore, SAVE RETURN and RESTURE RETURN can be used to push and pop the current return address, enabling proper recursion, as long as the programmer is careful. The downside to this is that it does not play well with argument passing. All variables are still global. This means that passing arguments to a recursive function has to be done either by pushing them on the stack beforehand, or by setting global variables that the functions will push and pop themselves. (This program does the latter.) At the same time, the language syntax demands that all functions take at least one argument, so a dummy argument must be passed. To obtain a recursive function that uses the argument it is given, it is necessary to write a front-end function that uses its argument to pass it through the actual function in the manner described above. This is also shown. In this program, F. and M. are the front ends, taking an argument and using it to set N, then calling either FREC. or MREC., which are the actual recursive functions, with a dummy zero argument.  NORMAL MODE IS INTEGER R SET UP STACK SPACE DIMENSION STACK(100) SET LIST TO STACK R DEFINE RECURSIVE FUNCTIONS R INPUT ARGUMENT ASSUMED TO BE IN N INTERNAL FUNCTION(DUMMY) ENTRY TO FREC. WHENEVER N.LE.0, FUNCTION RETURN 1 SAVE RETURN SAVE DATA N N = N-1 N = FREC.(0) X = MREC.(0) RESTORE DATA N RESTORE RETURN FUNCTION RETURN N-X END OF FUNCTION INTERNAL FUNCTION(DUMMY) ENTRY TO MREC. WHENEVER N.LE.0, FUNCTION RETURN 0 SAVE RETURN SAVE DATA N N = N-1 N = MREC.(0) X = FREC.(0) RESTORE DATA N RESTORE RETURN FUNCTION RETURN N-X END OF FUNCTION R DEFINE FRONT-END FUNCTIONS THAT CAN BE CALLED WITH ARGMT INTERNAL FUNCTION(NN) ENTRY TO F. N = NN FUNCTION RETURN FREC.(0) END OF FUNCTION INTERNAL FUNCTION(NN) ENTRY TO M. N = NN FUNCTION RETURN MREC.(0) END OF FUNCTION R PRINT F(0..19) AND M(0..19) THROUGH SHOW, FOR I=0, 1, I.GE.20SHOW PRINT FORMAT FMT,I,F.(I),I,M.(I) VECTOR VALUES FMT = 0$2HF(,I2,4H) = ,I2,S8,2HM(,I2,4H) = ,I2*$END OF PROGRAM Output: 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 ## 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); Output: 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6 ## Mathematica/Wolfram Language 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)) ).  ## MiniScript f = function(n) if n > 0 then return n - m(f(n - 1)) return 1end function m = function(n) if n > 0 then return n - f(m(n - 1)) return 0end function print f(12)print m(12) Output: 8 7 ## 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  ## Modula-2 MODULE MutualRecursion;FROM InOut IMPORT WriteCard, WriteString, WriteLn; TYPE Fn = PROCEDURE(CARDINAL): CARDINAL; PROCEDURE F(n: CARDINAL): CARDINAL;BEGIN IF n=0 THEN RETURN 1; ELSE RETURN n-M(F(n-1)); END;END F; PROCEDURE M(n: CARDINAL): CARDINAL;BEGIN IF n=0 THEN RETURN 0; ELSE RETURN n-F(M(n-1)); END;END M; (* Print the first few values of one of the functions *)PROCEDURE Show(name: ARRAY OF CHAR; fn: Fn); CONST Max = 15; VAR i: CARDINAL;BEGIN WriteString(name); WriteString(": "); FOR i := 0 TO Max DO WriteCard(fn(i), 0); WriteString(" "); END; WriteLn;END Show; (* Show the first values of both F and M *)BEGIN Show("F", F); Show("M", M);END MutualRecursion. Output: F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 M: 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9  ## 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): int proc f(n: int): int = if n == 0: 1 else: n - m(f(n-1)) proc m(n: int): int = if n == 0: 0 else: n - f(m(n-1)) for i in 1 .. 10: echo f(i) echo m(i) ## 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)); }}  ## 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;} ## 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 - ; 0 20 seqFrom map(#F) println0 20 seqFrom 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]  ## 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))))))) //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


## Phix

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

with javascript_semantics
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

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";?> ## Picat Here are two approaches, both using tabling. For small values (say N < 50) tabling is not really needed. ### Tabled functions tablef(0) = 1.f(N) = N - m(f(N-1)), N > 0 => true. tablem(0) = 0.m(N) = N - f(m(N-1)), N > 0 => true. ### Tabled predicates Translation of: Prolog tablefemale(0,1).female(N,F) :- N>0, N1 = N-1, female(N1,R), male(R, R1), F = N-R1. tablemale(0,0).male(N,F) :- N>0, N1 = N-1, male(N1,R), female(R, R1), F = N-R1. ### Test go => N = 30, println(func), test_func(N), println(pred), test_pred(N), nl. nl. % Testing the function based approachtest_func(N) => println([M : I in 0..N, male(I,M)]), println([F : I in 0..N, female(I,F)]), nl. % Testing the predicate approachtest_pred(N) => println([M : I in 0..N, male(I,M)]), println([F : I in 0..N, female(I,F)]), nl. Output: func [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] [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] pred [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] [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] ### Larger values For larger values, tabling is essential and then one can discern that the predicate based approach is a little faster. Here are the times for testing N=1 000 000: • func: 1.829s • pred: 1.407s ## 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). ## Quackery  forward is f ( n --> n ) [ dup 0 = if done dup 1 - recurse f - ] is m ( n --> n ) [ dup 0 = iff 1+ done dup 1 - recurse m - ] resolves f ( n --> n ) say "f = " 20 times [ i^ f echo sp ] cr say "m = " 20 times [ i^ m echo sp ] cr 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  ## 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)) ## 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)))))) ## Raku (formerly 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  ## 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] 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] ## 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 for lim+1; 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 Shown at three-quarter size.)  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 for lim+1 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 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 for aLim+1; call F(J); call M(j) if lim<0 then iterate 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")=" right( aLim, w)if lim>0 then say 'Fs=' Fs; else say 'F('aLim")=" right($f.aLim, w)if lim>0  then  say 'Ms='   Ms;        else  say  'M('aLim")="     right($m.aLIM, w)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 ## 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"); 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|    {|i| seq.call(i)}.map(^20).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.

## Tailspin

 templates male  when <=0> do 0 !  otherwise def n: $;$n - 1 -> male -> female -> $n -$ !end male templates female  when <=0> do 1 !  otherwise def n: $;$n - 1 -> female -> male -> $n -$ !end female 0..10 -> 'M$;:$->male; F$;:$->female;' -> !OUT::write 
Output:
M0: 0 F0: 1
M1: 0 F1: 1
M2: 1 F2: 2
M3: 2 F3: 2
M4: 2 F4: 3
M5: 3 F5: 3
M6: 4 F6: 4
M7: 4 F7: 5
M8: 5 F8: 5
M9: 6 F9: 6
M10: 6 F10: 6


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

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

## Vala

int F(int n) {   if (n == 0) return 1;  return n - M(F(n - 1));} int M(int n) {   if (n == 0) return 0;  return n - F(M(n - 1));} void main() {  print("n : ");  for (int s = 0; s < 25; s++){    print("%2d ", s);  }  print("\n------------------------------------------------------------------------------\n");  print("F : ");  for (int s = 0; s < 25; s++){    print("%2d ", F(s));  }  print("\nM : ");  for (int s = 0; s < 25; s++){    print("%2d ", M(s));  }}
Output:
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


## VBA

Private Function F(ByVal n As Integer) As Integer    If n = 0 Then        F = 1    Else        F = n - M(F(n - 1))    End IfEnd Function Private Function M(ByVal n As Integer) As Integer    If n = 0 Then        M = 0    Else        M = n - F(M(n - 1))    End IfEnd 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 iEnd Sub
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 

## Wren

var M  // forward declaration var F = Fn.new { |n|    if (n == 0) return 1    return n - M.call(F.call(n-1))} M = Fn.new { |n|    if (n == 0) return 0    return n - F.call(M.call(n-1))} System.write("F(0..20): ")(0..20).each { |i| System.write("%(F.call(i))  ") }System.write("\nM(0..20): ")(0..20).each { |i| System.write("%(M.call(i))  ") }System.print()
Output:
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


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


## Yabasic

Translation of: AWK
// User defined functionssub 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 "###";nextprintfor i = 0 to 20    print M(i) using "###";nextprint

## 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)
`