Mutual recursion: Difference between revisions
Content deleted Content added
Added FreeBASIC |
Added PascalABC.NET |
||
(98 intermediate revisions by 46 users not shown) | |||
Line 18:
then state this rather than give a solution by other means).
<br><br>
=={{header|8080 Assembly}}==
The 8080 processor has built-in support for recursion, at the instruction level.
The processor keeps a <em>stack pointer</em>, called <code>SP</code>,
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 <code>call</code> instruction, which pushes the location of the
next instruction onto the stack, and then jumps to the given location. Its counterpart is the
<code>ret</code> instruction, which pops a location from the stack and jumps there.
There are also <code>push</code> and <code>pop</code> 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.
<syntaxhighlight lang="8080asm"> 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
ret
one: 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=0
floop: 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=0
mloop: 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 space
pdgt: adi '0' ; ASCII
mov e,a
mvi c,2
call 5
mvi e,' ' ; Space
mvi c,2
jmp 5 ; Tail call optimization
fpfx: db 'F: $'
mpfx: db 13,10,'M: $'</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|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.
<syntaxhighlight lang="abap">
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 ) }| ) }|, /.
</syntaxhighlight>
{{output}}
<pre>
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
</pre>
=={{header|ABC}}==
<syntaxhighlight lang="ABC">HOW TO RETURN f n:
IF n=0: RETURN 1
RETURN n - m f (n-1)
HOW TO RETURN m n:
IF n=0: RETURN 0
RETURN n - f m (n-1)
WRITE "F:"
FOR n IN {0..15}: WRITE f n
WRITE /
WRITE "M:"
FOR n IN {0..15}: WRITE m n
WRITE /</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|ACL2}}==
<
(defun f (n)
(declare (xargs :mode :program))
Line 31 ⟶ 203:
(if (zp n)
0
(- n (f (m (1- n)))))))</
=={{header|Ada}}==
<
procedure Mutual_Recursion is
function M(N : Integer) return Integer;
Line 61 ⟶ 233:
Put_Line(Integer'Image(M(I)));
end loop;
end Mutual_recursion;</
{{Works with|Ada 2012}}
<
procedure Mutual_Recursion is
function M(N: Natural) return Natural;
Line 83 ⟶ 255:
end loop;
end Mutual_recursion;</
=={{header|Aime}}==
{{trans|C}}
<
integer M(integer n);
Line 129 ⟶ 301:
o_byte('\n');
return 0;
}</
=={{header|ALGOL 68}}==
Line 137 ⟶ 309:
{{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 f = (INT n)INT:
Line 157 ⟶ 329:
OD;
new line(stand out)
)</
{{out}}
<pre>
Line 165 ⟶ 337:
=={{header|ALGOL W}}==
<
% define mutually recursive funtions F and M that compute the elements %
% of the Hofstadter Female and Male sequences %
Line 182 ⟶ 354:
for i := 0 until 20 do writeon( M( i ) );
end.</
=={{header|APL}}==
{{works with|Dyalog APL}}
<syntaxhighlight lang="apl">f ← {⍵=0:1 ⋄ ⍵-m∇⍵-1}
m ← {⍵=0:0 ⋄ ⍵-f∇⍵-1}
⍉'nFM'⍪↑(⊢,f,m)¨0,⍳20</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|AppleScript}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{Out}}
<syntaxhighlight lang="applescript">{{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}}</syntaxhighlight>
=={{header|ARM Assembly}}==
Unlike on the x86 family of processors, the ARM instruction set does not include specialized
<code>call</code> and <code>ret</code> instructions. However, the program counter is a visible
register (<code>r15</code>, also called <code>pc</code>), 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, <code>r13</code> is used as the system stack pointer and is therefore also
called <code>sp</code>, and <code>r14</code> is used to store the return address for
a function, and is therefore also called the *link register* or <code>lr</code>.
The assembler recognizes <code>push {x}</code> and <code>pop {x}</code> instructions, though these
are really pseudoinstructions, that generate the exact same machine code as
<code>ldmia r13!,{x}</code> and <code>stmdb r13!,{x}</code>,
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
(<code>bl</code>). These are the same as <code>mov r14,pc ; mov/ldr pc,<destination></code>, 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).
<syntaxhighlight lang="text">.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 0
1: 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 stdout
pstr: 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
.data
fmsg: .ascii "\3F: "
mmsg: .ascii "\3M: "
dstr: .ascii "\2"
dgt: .ascii "* "
nl: .ascii "\1\n"</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Arturo}}==
<syntaxhighlight lang="rebol">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 ""
]</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|AutoHotkey}}==
<
i := A_Index-1, t .= "`n" i "`t " M(i) "`t " F(i)
MsgBox x`tmale`tfemale`n%t%
Line 195 ⟶ 619:
M(n) {
Return n ? n - F(M(n-1)) : 0
}</
{{trans|C}}
Line 201 ⟶ 625:
This one is an alternative to the above.
<
Return
Line 231 ⟶ 655:
MsgBox % "male:`n" . male
MsgBox % "female:`n" . female
}</
=={{header|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.
<syntaxhighlight lang="awk">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}}
<pre>
$ 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
</pre>
=={{header|BaCon}}==
<syntaxhighlight lang="freebasic">' 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</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|BASIC}}==
{{works with|QBasic}}
<
DECLARE FUNCTION m! (n!)
Line 278 ⟶ 735:
m = f(m(n - 1))
END IF
END FUNCTION</
==={{header|BBC BASIC}}===
<
PRINT "F sequence:"
FOR i% = 0 TO 20
Line 296 ⟶ 753:
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}}
<pre>
Line 304 ⟶ 761:
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12
</pre>
==={{header|IS-BASIC}}===
<syntaxhighlight lang="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</syntaxhighlight>
=={{header|BASIC256}}==
<syntaxhighlight lang="basic256"># Rosetta Code problem: http://rosettacode.org/wiki/Mutual_recursion
# by Jjuanhdez, 06/2022
n = 24
print "n : ";
for i = 0 to n : print ljust(i, 3); : next i
print chr(10); ("-" * 78)
print "F : ";
for i = 0 to n : print ljust(F(i), 3); : next i
print chr(10); "M : ";
for i = 0 to n : print ljust(M(i), 3); : next i
end
function F(n)
if n = 0 then return 0 else return n - M(F(n-1))
end function
function M(n)
if n = 0 then return 0 else return n - F(M(n-1))
end function</syntaxhighlight>
=={{header|Bc}}==
<syntaxhighlight lang="bc">cat mutual_recursion.bc:
define f(n) {
if ( n == 0 ) return(1);
return(n - m(f(n-1)));
Line 315 ⟶ 820:
if ( n == 0 ) return(0);
return(n - f(m(n-1)));
}</
{{works with|GNU bc}}
Line 321 ⟶ 826:
POSIX bc doesn't have the <tt>print</tt> statement.
<
for(i=0; i < 19; i++) {
print f(i); print " ";
Line 329 ⟶ 834:
print m(i); print " ";
}
print "\n";
quit</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|BCPL}}==
<syntaxhighlight lang="bcpl">get "libhdr"
// Mutually recursive functions
let f(n) = n=0 -> 1, n - m(f(n-1))
and m(n) = n=0 -> 0, n - f(m(n-1))
// Print f(0..15) and m(0..15)
let start() be
$( writes("F:")
for i=0 to 15 do
$( writes(" ")
writen(f(i))
$)
writes("*NM:")
for i=0 to 15 do
$( writes(" ")
writen(m(i))
$)
writes("*N")
$)</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|BQN}}==
<syntaxhighlight lang="bqn">F ← {0:1; 𝕩-M F𝕩-1}
M ← {0:0; 𝕩-F M𝕩-1}
⍉"FM"∾>(F∾M)¨↕15</syntaxhighlight>
{{out}}
<pre>┌─
╵ 'F' 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9
'M' 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9
┘</pre>
=={{header|Bracmat}}==
<
(M=.!arg:0&0|!arg+-1*F$(M$(!arg+-1)));
Line 339 ⟶ 891:
-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</
=={{header|Brat}}==
<
male = { n |
Line 357 ⟶ 909:
p 0.to(20).map! { n | female n }
p 0.to(20).map! { n | male n }</
=={{header|Bruijn}}==
Normally it's not possible to call functions before they are defined. We can still induce mutual recursion using its [[Variadic_fixed-point_combinator|variadic fixed-point combinator]].
<syntaxhighlight lang="bruijn">
:import std/Combinator .
:import std/Number .
:import std/List .
f' [[[=?0 (+1) (0 - (1 (2 --0)))]]]
m' [[[=?0 (+0) (0 - (2 (1 --0)))]]]
f ^(y* (f' : {}m'))
m _(y* (f' : {}m'))
:test ((f (+0)) =? (+1)) ([[1]])
:test ((m (+0)) =? (+0)) ([[1]])
:test ((f (+4)) =? (+3)) ([[1]])
:test ((m (+4)) =? (+2)) ([[1]])
:test ((f (+15)) =? (+9)) ([[1]])
:test ((m (+15)) =? (+9)) ([[1]])
</syntaxhighlight>
=={{header|C}}==
Line 363 ⟶ 938:
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 <stdlib.h>
Line 392 ⟶ 967:
printf("\n");
return EXIT_SUCCESS;
}</
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">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;
}
}
}</syntaxhighlight>
=={{header|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 <vector>
#include <iterator>
Line 431 ⟶ 1,029:
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.
Line 437 ⟶ 1,035:
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.
<
{
public:
Line 454 ⟶ 1,052:
if ( n == 0 ) return 0;
return n - F(M(n-1));
}</
=={{header|Ceylon}}==
<
=> if (n > 0)
then n - m(f(n-1))
Line 494 ⟶ 1,069:
printAll((0:20).map(f));
printAll((0:20).map(m));
}</
{{out}}
Line 504 ⟶ 1,079:
=={{header|Clojure}}==
<
(defn M [n]
Line 514 ⟶ 1,089:
(if (zero? n)
1
(- n (M (F (dec n))))))</
=={{header|CLU}}==
<syntaxhighlight lang="clu">
% To declare things you can either write an .spc file or you can use
% the clu file itself as a specfile. For a small program a common
% idiom is to spec and compile the same source file:
%
% pclu -spec mutrec.clu -clu mutrec.clu
%
start_up = proc ()
print_first_16("F", F)
print_first_16("M", M)
end start_up
% Print the first few values for F and M
print_first_16 = proc (name: string, fn: proctype (int) returns (int))
po: stream := stream$primary_output()
stream$puts(po, name || ":")
for i: int in int$from_to(0, 15) do
stream$puts(po, " " || int$unparse(fn(i)))
end
stream$putl(po, "")
end print_first_16
F = proc (n: int) returns (int)
if n = 0 then
return (1)
else
return (n - M(F(n-1)))
end
end F
M = proc (n: int) returns (int)
if n = 0 then
return (0)
else
return (n - F(M(n-1)))
end
end M
</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|CoffeeScript}}==
<
F = (n) ->
if n is 0 then 1 else n - M F n - 1
Line 526 ⟶ 1,144:
console.log [0...20].map F
console.log [0...20].map M
</syntaxhighlight>
{{out}}
<syntaxhighlight lang="text">
> 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 ]
</syntaxhighlight>
=={{header|Common Lisp}}==
<
(if (zerop n)
0
Line 545 ⟶ 1,163:
(if (zerop n)
1
(- n (m (f (- n 1))))))</
=={{header|D}}==
<
int male(in int n) pure nothrow {
Line 561 ⟶ 1,179:
20.iota.map!female.writeln;
20.iota.map!male.writeln;
}</
{{out}}
<pre>[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]</pre>
=={{header|Dart}}==
<
int F(int n) => n==0?0:n-M(F(n-1));
Line 606 ⟶ 1,196:
print("M: $m");
print("F: $f");
}</
=={{header|Delphi}}==
<syntaxhighlight lang="delphi">
unit Hofstadter;
Line 638 ⟶ 1,228:
end.
</syntaxhighlight>
=={{header|Déjà Vu}}==
<syntaxhighlight lang="dejavu">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 )</syntaxhighlight>
{{out}}
<pre>0 1
0 1
1 2
2 2
2 3
3 3
4 4
4 5
5 5
6 6
6 6 </pre>
=={{header|Draco}}==
<syntaxhighlight lang="draco">/* We need to predeclare M if we want F to be able to see it.
* This is done using 'extern', same as if it had been in a
* different compilation unit. */
extern M(byte n) byte;
/* Mutually recursive functions */
proc F(byte n) byte:
if n=0 then 1 else n - M(F(n-1)) fi
corp
proc M(byte n) byte:
if n=0 then 0 else n - F(M(n-1)) fi
corp
/* Show the first 16 values of each */
proc nonrec main() void:
byte i;
write("F:");
for i from 0 upto 15 do write(F(i):2) od;
writeln();
write("M:");
for i from 0 upto 15 do write(M(i):2) od;
writeln()
corp</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Dyalect}}==
<syntaxhighlight lang="dyalect">func f(n) {
n == 0 ? 1 : n - m(f(n-1))
}
and m(n) {
n == 0 ? 0 : n - f(m(n-1))
}
print( (0..20).Map(i => f(i)).ToArray() )
print( (0..20).Map(i => m(i)).ToArray() )</syntaxhighlight>
=={{header|E}}==
Line 646 ⟶ 1,307:
Recursive def:
<
fn n { if (n <=> 0) { 1 } else { n - M(F(n - 1)) } },
fn n { if (n <=> 0) { 0 } else { n - F(M(n - 1)) } },
]</
Forward declaration:
<
def F(n) { return if (n <=> 0) { 1 } else { n - M(F(n - 1)) } }
bind M(n) { return if (n <=> 0) { 0 } else { n - F(M(n - 1)) } }</
<code>def M</code> binds <var>M</var> to a promise, and stashes the ''resolver'' for that promise where <code>bind</code> can get to it. When <code>def F...</code> is executed, the function F closes over the promise which is the value of M. <code>bind M...</code> uses the resolver to resolve <var>M</var> to the provided definition. The recursive def operates similarly, except that it constructs promises for every variable on the left side (<code>[F, M]</code>), executes the right side (<code>[fn ..., fn ...]</code>) and collects the values, then resolves each promise to its corresponding value.
But you don't have to worry about that to use it.
=={{header|EasyLang}}==
<syntaxhighlight lang=text>
funcdecl M n .
func F n .
if n = 0
return 1
.
return n - M F (n - 1)
.
func M n .
if n = 0
return 0
.
return n - F M (n - 1)
.
for i = 0 to 15
write F i & " "
.
print ""
for i = 0 to 15
write M i & " "
.
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 709 ⟶ 1,395:
end
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Elena}}==
{{trans|Smalltalk}}
ELENA 6.x :
<syntaxhighlight lang="elena">import extensions;
import system'collections;
F = (n => (n == 0) ? 1 : (n - M(F(n-1))) );
M = (n => (n == 0) ? 0 : (n - F(M(n-1))) );
public program()
{
var ra := new ArrayList();
var rb := new ArrayList();
for(int i := 0; i <= 19; i += 1)
{
ra.append(F(i));
rb.append(M(i))
};
console.printLine(ra.asEnumerable());
console.printLine(rb.asEnumerable())
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Elixir}}==
<
def f(0), do: 1
def f(n), do: n - m(f(n - 1))
Line 725 ⟶ 1,440:
IO.inspect Enum.map(0..19, fn n -> MutualRecursion.f(n) end)
IO.inspect Enum.map(0..19, fn n -> MutualRecursion.m(n) end)</
{{out}}
Line 731 ⟶ 1,446:
[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]
</pre>
=={{header|EMal}}==
<syntaxhighlight lang="emal">
fun F ← <int n|when(n æ 0, 1, n - M(F(n - 1)))
fun M ← <int n|when(n æ 0, 0, n - F(M(n - 1)))
write("F: ")
range(0, 21).list(<int n|write(F(n) + ", "))
writeLine("...")
write("M: ")
range(0, 21).list(<int n|write(M(n) + ", "))
writeLine("...")
</syntaxhighlight>
{{out}}
<pre>
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, ...
</pre>
=={{header|Erlang}}==
<
-export([mutrec/0, f/1, m/1]).
Line 746 ⟶ 1,478:
io:format("~n", []),
lists:map(fun(X) -> io:format("~w ", [m(X)]) end, lists:seq(0,19)),
io:format("~n", []).</
=={{header|Euphoria}}==
<
function F(integer n)
Line 769 ⟶ 1,501:
end function
idM = routine_id("M")</
=={{header|F_Sharp|F#}}==
<
match n with
| 0 -> 1
Line 780 ⟶ 1,512:
match n with
| 0 -> 0
| _ -> n - (f (m (n-1)))</
Like OCaml, the <code>let '''rec''' ''f'' .. '''and''' ''m'' ...</code> construct indicates that the functions call themselves (<code>'''rec'''</code>) and each other (<code>'''and'''</code>).
Line 786 ⟶ 1,518:
=={{header|Factor}}==
In Factor, if you need a word before it's defined, you have to <code>DEFER:</code> it.
<syntaxhighlight lang="text">DEFER: F
: M ( n -- n' ) dup 0 = [ dup 1 - M F - ] unless ;
: F ( n -- n' ) dup 0 = [ drop 1 ] [ dup 1 - F M - ] if ;</
=={{header|FALSE}}==
<
[$[$1-m;!f;!- ]? ]m:
[0[$20\>][\$@$@!." "1+]#%%]t:
f; t;!"
"m; t;!</
=={{header|Fantom}}==
<
class Main
{
Line 823 ⟶ 1,555:
}
}
</syntaxhighlight>
=={{header|FOCAL}}==
<syntaxhighlight lang="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,N
01.30 T !"M(0..15)"
01.40 F X=0,15;S N=X;D 5;T %1,N
01.50 T !
01.60 Q
04.01 C--N = F(N)
04.10 I (N(D)),4.11,4.2
04.11 S N(D)=1;R
04.20 S D=D+1;S N(D)=N(D-1)-1;D 4;D 5
04.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.2
05.11 R
05.20 S D=D+1;S N(D)=N(D-1)-1;D 5;D 4
05.30 S D=D-1;S N(D)=N(D)-N(D+1)</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Forth}}==
Forward references required for mutual recursion may be set up using DEFER.
<
: f ( n -- n )
Line 841 ⟶ 1,600:
' 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</
=={{header|Fortran}}==
Line 848 ⟶ 1,607:
{{works with|Fortran|95 and later}}
<
implicit none
contains
Line 871 ⟶ 1,630:
end function f
end module</
I've added the attribute <tt>pure</tt> so that we can use them in a <tt>forall</tt> statement.
<
use MutualRec
implicit none
Line 891 ⟶ 1,650:
write(*,'(20I3)') ra
end program testmutrec</
=={{header|FreeBASIC}}==
<
' Need forward declaration of M as it's used
Line 926 ⟶ 1,685:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 934 ⟶ 1,693:
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
</pre>
=={{header|Fōrmulæ}}==
{{FormulaeEntry|page=https://formulae.org/?script=examples/Mutual_recursion}}
'''Solution'''
[[File:Fōrmulæ - Mutual recursion 01.png]]
[[File:Fōrmulæ - Mutual recursion 02.png]]
[[File:Fōrmulæ - Mutual recursion 03.png]]
=={{header|FutureBasic}}==
<syntaxhighlight lang="futurebasic">
def fn F( n as long ) as long
def fn M( n as long ) as long
local fn F( n as long ) as long
long result
if n == 0 then exit fn = 1
result = n - fn M( fn F( n-1 ) )
end fn = result
local fn M( n as long ) as long
long result
if n == 0 then exit fn = 0
result = n - fn F( fn M( n-1 ) )
end fn = result
long i, counter
counter = 0
for i = 0 to 19
printf @"%3ld\b", fn F( i )
counter++
if counter mod 5 == 0 then print : counter = 0
next
print : print
counter = 0
for i = 0 to 19
printf @"%3ld\b", fn M( i )
counter++
if counter mod 5 == 0 then print : counter = 0
next
NSLog( @"%@", fn WindowPrintViewString( 1 ) )
HandleEvents
</syntaxhighlight>
{{output}}
<pre>
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
</pre>
=={{header|Go}}==
It just works. No special pre-declaration is necessary.
<
import "fmt"
Line 960 ⟶ 1,786:
}
fmt.Println()
}</
=={{header|Groovy}}==
Solution:
<
f = { n -> n == 0 ? 1 : n - m(f(n-1)) }
m = { n -> n == 0 ? 0 : n - f(m(n-1)) }</
Test program:
<
println 'm(0..20): ' + (0..20).collect { m(it) }</
{{out}}
Line 978 ⟶ 1,804:
=={{header|Haskell}}==
Haskell's definitions constructs (at the top level, or inside a <code>let</code> or <code>where</code> construct) are always mutually-recursive:
<
f n | n > 0 = n - m (f $ n-1)
Line 986 ⟶ 1,812:
main = do
print $ map f [0..19]
print $ map m [0..19]</
=={{header|Icon}} and {{header|Unicon}}==
<
every write(F(!arglist)) # F of all arguments
end
Line 1,001 ⟶ 1,827:
if integer(n) >= 0 then
return (0 = n) | n - F(M(n-1))
end</
=={{header|Idris}}==
<
F : Nat -> Nat
F Z = (S Z)
Line 1,012 ⟶ 1,838:
M Z = Z
M (S n) = (S n) `minus` F(M(n))
}</
=={{header|Io}}==
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>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)</pre>
=={{header|J}}==
<
M =: 0:`(- F @ $: @ <:) @.* M."0</
Example use:
<
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
=={{header|Java}}==
Replace translation (that doesn't compile) with a Java native implementation.
<syntaxhighlight lang="java">
import java.util.HashMap;
import java.util.Map;
public
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.
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;
}
}
</syntaxhighlight>
{{out}}
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
=={{header|JavaScript}}==
<
return (num === 0) ? 1 : num - m(f(num - 1));
}
Line 1,065 ⟶ 1,970:
//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}}
<pre>1,1,2,2,3,3,4,5,5,6,6,7,8,8,9,9,10,11,11,12
Line 1,071 ⟶ 1,976:
ES6 implementation
<
var m = num => (num === 0) ? 0 : num - f(m(num - 1));
Line 1,084 ⟶ 1,989:
//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
<
=={{header|jq}}==
jq supports mutual recursion but requires functions to be defined before they are used.
In the present case, this can be accomplished by
He we define F and M as arity-0 filters:
<syntaxhighlight lang="jq">
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;</syntaxhighlight>Example:<syntaxhighlight lang="jq">
[range(0;20) | F],
[range(0;20) | M]</
[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|Jsish}}==
<syntaxhighlight lang="javascript">/* 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!=
*/</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Julia}}==
<
M(n) = n < 1 ? zero(n) : n - F(M(n - 1))</
{{out}}
<pre>
Line 1,113 ⟶ 2,051:
([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])
</pre>
=={{header|Kotlin}}==
<syntaxhighlight lang="scala">// 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((n + 2) * 3))
print("F :")
for (i in 0..n) print("%3d".format(f(i)))
println()
print("M :")
for (i in 0..n) print("%3d".format(m(i)))
println()
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Lambdatalk}}==
<syntaxhighlight lang="scheme">
{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
</syntaxhighlight>
The naïve version is very slow, {F 80} requires 3800 ms on a recent laptop, so let's memoize:
<syntaxhighlight lang="scheme">
{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
</syntaxhighlight>
=={{header|Liberty BASIC}}==
<syntaxhighlight lang="lb">
print "F sequence."
for i = 0 to 20
Line 1,143 ⟶ 2,170:
end if
end function
</syntaxhighlight>
{{out}}
<pre>F sequence.
Line 1,151 ⟶ 2,178:
=={{header|LibreOffice Basic}}==
<
'// Utility functions
Line 1,245 ⟶ 2,272:
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
</syntaxhighlight>
=={{header|Logo}}==
Like Lisp, symbols in Logo are late-bound so no special syntax is required for forward references.
<
if 0 = :n [output 0]
output :n - f m :n-1
Line 1,262 ⟶ 2,289:
[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]</
=={{header|LSL}}==
To test it yourself; rez a box on the ground, and add the following as a New Script.
<
integer f(integer n) {
if(n==0) {
Line 1,295 ⟶ 2,322:
llOwnerSay(llList2CSV(llParseString2List(s, [" "], [])));
}
}</
{{out}}
<pre>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
Line 1,301 ⟶ 2,328:
=={{header|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</
=={{header|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.
<syntaxhighlight lang="m2000 interpreter">
\\ 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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|M4}}==
<
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')</
=={{header|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 <code>SET LIST TO array</code>.
Once this is done, however, variables can be pushed and popped
(using the <code>SAVE</code> and <code>RESTORE</code> commands).
Furthermore, <code>SAVE RETURN</code> and <code>RESTURE RETURN</code> 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, <code>F.</code> and <code>M.</code> are the front ends, taking an
argument and using it to set <code>N</code>, then calling either <code>FREC.</code>
or <code>MREC.</code>, which are the actual recursive functions, with a dummy zero argument.
<syntaxhighlight lang="mad"> 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.20
SHOW 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</syntaxhighlight>
{{out}}
<pre>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</pre>
=={{header|Maple}}==
<syntaxhighlight lang="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);</syntaxhighlight>
{{Out|Output}}
<pre>1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6
0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6</pre>
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Without caching:
<
m[0]:=0
f[n_]:=n-m[f[n-1]]
m[n_]:=n-f[m[n-1]]</
With caching:
<
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):
<
f /@ Range[30]</
gives back:
<
{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}</
=={{header|MATLAB}}==
female.m:
<
if n == 0
Line 1,348 ⟶ 2,603:
Fn = n - male(female(n-1));
end</
male.m:
<
if n == 0
Line 1,359 ⟶ 2,614:
Mn = n - female(male(n-1));
end</
{{out}}
<
>> arrayfun(@female,n)
Line 1,373 ⟶ 2,628:
ans =
0 0 1 2 2 3 4 4 5 6 6</
=={{header|Maxima}}==
<
m[0]: 0$
f[n] := n - m[f[n - 1]]$
Line 1,399 ⟶ 2,654:
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6]
remfunction(f, m)$</
=={{header|Mercury}}==
<syntaxhighlight lang="text">
:- module mutual_recursion.
:- interface.
Line 1,423 ⟶ 2,678:
m(N) = ( if N = 0 then 0 else N - f(m(N - 1)) ).
</syntaxhighlight>
=={{header|MiniScript}}==
<syntaxhighlight lang="miniscript">f = function(n)
if n > 0 then return n - m(f(n - 1))
return 1
end function
m = function(n)
if n > 0 then return n - f(m(n - 1))
return 0
end function
print f(12)
print m(12)</syntaxhighlight>
{{out}}
<pre>8
7</pre>
=={{header|MiniZinc}}==
<syntaxhighlight lang="minizinc">
function var int: F(var int:n) =
if n == 0 then
1
else
n - M(F(n - 1))
endif;
function var int: M(var int:n) =
if (n == 0) then
0
else
n - F(M(n - 1))
endif;
</syntaxhighlight>
=={{header|MMIX}}==
<
GREG @
Line 1,503 ⟶ 2,792:
LDA $255,NL
TRAP 0,Fputs,StdOut
TRAP 0,Halt,0</
{{out}}
Line 1,510 ⟶ 2,799:
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
=={{header|Modula-2}}==
<syntaxhighlight lang="modula2">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.</syntaxhighlight>
{{out}}
<pre>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 </pre>
=={{header|Nemerle}}==
<
using System.Console;
Line 1,534 ⟶ 2,865:
foreach (n in [0 .. 20]) Write("{0} ", M(n));
}
}</
=={{header|Nim}}==
<
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))
Line 1,549 ⟶ 2,880:
for i in 1 .. 10:
echo f(i)
echo m(i)</
=={{header|Oberon-2}}==
{{trans|Modula-2}}
<syntaxhighlight lang="oberon2">
MODULE MutualRecursion;
IMPORT Out;
TYPE
Fn = PROCEDURE(n:INTEGER):INTEGER;
PROCEDURE^ M(n:INTEGER):INTEGER;
PROCEDURE F(n:INTEGER):INTEGER;
BEGIN
IF n=0 THEN RETURN 1
ELSE RETURN n-M(F(n-1))
END;
END F;
PROCEDURE M(n:INTEGER):INTEGER;
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:INTEGER;
BEGIN
Out.String(name);
Out.String(": ");
FOR i := 0 TO Max DO
Out.Int(fn(i),0);
Out.String(" ");
END;
Out.Ln;
END Show;
(* Show the first values of both F and M *)
BEGIN
Show("F", F);
Show("M", M);
END MutualRecursion.
</syntaxhighlight>
{{out}}
<pre>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 </pre>
=={{header|Objeck}}==
{{trans|C}}
<syntaxhighlight lang="objeck">
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));
}
}
</syntaxhighlight>
=={{header|Objective-C}}==
Line 1,555 ⟶ 2,961:
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 <tt>interface</tt> block that is like declaration of functions in C code.
<
@interface Hofstadter : NSObject
Line 1,588 ⟶ 2,994:
printf("\n");
return 0;
}</
=={{header|OCaml}}==
<
| 0 -> 1
| n -> n - m(f(n-1))
Line 1,622 ⟶ 3,003:
| 0 -> 0
| n -> n - f(m(n-1))
;;</
The <code>let '''rec''' ''f'' ... '''and''' ''m'' ...</code> construct indicates that the functions call themselves (<code>'''rec'''</code>) and each other (<code>'''and'''</code>).
Line 1,631 ⟶ 3,012:
(The code is written to handle vectors, as the testing part shows)
<
for i = 1:length(n)
if (n(i) == 0)
Line 1,649 ⟶ 3,030:
endif
endfor
endfunction</
<
ra = F([0:19]);
rb = M([0:19]);
disp(ra);
disp(rb);</
=={{header|Oforth}}==
Line 1,662 ⟶ 3,042:
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).
<
Integer method: F
Line 1,673 ⟶ 3,053:
0 20 seqFrom map(#F) println
0 20 seqFrom map(#M) println</
{{out}}
Line 1,680 ⟶ 3,060:
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12]
</pre>
=={{header|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.
<syntaxhighlight lang="scheme">
(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
</syntaxhighlight>
=={{header|Order}}==
Line 1,685 ⟶ 3,078:
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.
<
#define ORDER_PP_DEF_8f \
Line 1,701 ⟶ 3,094:
//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))</
=={{header|Oz}}==
<
fun {F N}
if N == 0 then 1
Line 1,718 ⟶ 3,111:
in
{Show {Map {List.number 0 9 1} F}}
{Show {Map {List.number 0 9 1} M}}</
=={{header|PARI/GP}}==
<
M(n)=if(n,n-F(M(n-1)),0)</
=={{header|Pascal}}==
Line 1,728 ⟶ 3,121:
In Pascal we need to pre-declare functions/procedures; to do so, the <tt>forward</tt> statement is used.
<
{M definition comes after F which uses it}
Line 1,761 ⟶ 3,154:
end;
writeln;
end.</
=={{header|PascalABC.NET}}==
<syntaxhighlight lang="delphi">
##
function M(n: integer): integer; forward;
function F(n: integer): integer := n < 1 ? 1 : n - M(F(n - 1));
function M(n: integer): integer := n < 1 ? 0 : n - F(M(n - 1));
(0..19).select(x -> F(x)).println;
(0..19).select(x -> M(x)).println;
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Perl}}==
<
sub M { my $n = shift; $n ? $n - F(M($n-1)) : 0 }
Line 1,770 ⟶ 3,179:
foreach my $sequence (\&F, \&M) {
print join(' ', map $sequence->($_), 0 .. 19), "\n";
}</
{{out}}
<pre>
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
</pre>
=={{header|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.
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">forward</span> <span style="color: #008080;">function</span> <span style="color: #000000;">M</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">F</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">?</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">M</span><span style="color: #0000FF;">(</span><span style="color: #000000;">F</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)):</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">M</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">?</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">F</span><span style="color: #0000FF;">(</span><span style="color: #000000;">M</span><span style="color: #0000FF;">(</span><span style="color: #000000;">n</span><span style="color: #0000FF;">-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)):</span><span style="color: #000000;">0</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">20</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" %d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">F</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">20</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">" %d"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">M</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
Line 1,818 ⟶ 3,216:
=={{header|PHP}}==
<
function F($n)
{
Line 1,840 ⟶ 3,238:
echo implode(" ", $ra) . "\n";
echo implode(" ", $rb) . "\n";
?></
=={{header|Picat}}==
Here are two approaches, both using tabling. For small values (say N < 50) tabling is not really needed.
===Tabled functions===
<syntaxhighlight lang="picat">table
f(0) = 1.
f(N) = N - m(f(N-1)), N > 0 => true.
table
m(0) = 0.
m(N) = N - f(m(N-1)), N > 0 => true.</syntaxhighlight>
===Tabled predicates===
{{trans|Prolog}}
<syntaxhighlight lang="picat">table
female(0,1).
female(N,F) :-
N>0,
N1 = N-1,
female(N1,R),
male(R, R1),
F = N-R1.
table
male(0,0).
male(N,F) :-
N>0,
N1 = N-1,
male(N1,R),
female(R, R1),
F = N-R1.</syntaxhighlight>
===Test===
<syntaxhighlight lang="picat">go =>
N = 30,
println(func),
test_func(N),
println(pred),
test_pred(N),
nl.
nl.
% Testing the function based approach
test_func(N) =>
println([M : I in 0..N, male(I,M)]),
println([F : I in 0..N, female(I,F)]),
nl.
% Testing the predicate approach
test_pred(N) =>
println([M : I in 0..N, male(I,M)]),
println([F : I in 0..N, female(I,F)]),
nl.</syntaxhighlight>
{{out}}
<pre>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]</pre>
===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
=={{header|PicoLisp}}==
<
(if (=0 N)
1
Line 1,851 ⟶ 3,317:
(if (=0 N)
0
(- N (f (m (dec N)))) ) )</
=={{header|PL/I}}==
<
M: procedure (n) returns (fixed) recursive; /* 8/1/2010 */
Line 1,873 ⟶ 3,339:
put skip list ( F(i), M(i) );
end;
end test;</
=={{header|PostScript}}==
<syntaxhighlight lang="text">
/female{
/n exch def
Line 1,894 ⟶ 3,360:
}ifelse
}def
</syntaxhighlight>
{{libheader|initlib}}
<
/F {
{
Line 1,913 ⟶ 3,379:
}.
</syntaxhighlight>
=={{header|PowerShell}}==
<
if ($n -eq 0) { return 1 }
return $n - (M (F ($n - 1)))
Line 1,924 ⟶ 3,390:
if ($n -eq 0) { return 0 }
return $n - (F (M ($n - 1)))
}</
=={{header|Prolog}}==
<
female(N,F) :- N>0,
N1 is N-1,
Line 1,939 ⟶ 3,405:
male(N1,R),
female(R, R1),
F is N-R1.</
{{works with|GNU Prolog}}
<
mlist(S) :- for(X, 0, S), male(X, R), format('~d ', [R]), fail.</
'''Testing'''
Line 1,957 ⟶ 3,423:
The Pure definitions very closely maps to the mathematical definitions.
<
M 0 = 0;
F n = n - M(F(n-1)) if n>0;
M n = n - F(M(n-1)) if n>0;</
<
[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]</
=={{header|PureBasic}}==
<
Procedure F(n)
Line 2,008 ⟶ 3,475:
Input()
CloseConsole()
EndIf</
{{out}}
<pre>1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12
Line 2,015 ⟶ 3,482:
=={{header|Python}}==
{{works with|Python|3.0}}.<br>{{works with|Python|2.6}}<br>
<
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}}
Line 2,026 ⟶ 3,493:
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).
=={{header|Quackery}}==
See also [http://rosettacode.org/wiki/Even_or_odd#Quackery:_With_Anonymous_Mutual_Recursion Even or Odd#Quackery: With Anonymous Mutual recursion].
<syntaxhighlight lang="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</syntaxhighlight>
{{out}}
<pre>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 </pre>
=={{header|R}}==
<
M <- function(n) ifelse(n == 0, 0, n - F(M(n-1)))</
<
print.table(lapply(0:19, F))</
=={{header|Racket}}==
<syntaxhighlight lang="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))))))</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
A direct translation of the definitions of <math>F</math> and <math>M</math>:
<syntaxhighlight lang="raku" line>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;</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|REBOL}}==
<
Title: "Mutual Recursion"
URL: http://rosettacode.org/wiki/Mutual_Recursion
References: [http://en.wikipedia.org/wiki/Hofstadter_sequence#Hofstadter_Female_and_Male_sequences]
Line 2,054 ⟶ 3,569:
fs: [] ms: [] for i 0 19 1 [append fs f i append ms m i]
print ["F:" mold fs crlf "M:" mold ms]</
{{out}}
Line 2,060 ⟶ 3,575:
<pre>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]</pre>
=={{header|REFAL}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Prout 'F: ' <S F 0 14>>
};
F { 0 = 1; s.N = <- s.N <M <F <- s.N 1>>>>; };
M { 0 = 0; s.N = <- s.N <F <M <- s.N 1>>>>; };
S {
s.F s.N s.M, <Compare s.N s.M>: '+' = ;
s.F s.N s.M = <Mu s.F s.N> <S s.F <+ s.N 1> s.M>;
};</syntaxhighlight>
{{out}}
<pre>F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9
M: 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9</pre>
=={{header|REXX}}==
===vanilla===
This version uses vertical formatting of the output.
<
parse arg lim .;
do j=0
say pad 'F('jj") =" ff pad 'M('jj") ="
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) )</
Shown at three-quarter size.)
<pre style="font-size:75%">
F( 0) = 1 M( 0) = 0
F( 1) = 1 M( 1) = 0
Line 2,132 ⟶ 3,657:
This version uses memoization as well as a horizontal (aligned) output format.
<br><br>The optimization due to memoization is faster by many orders of magnitude.
<
parse arg lim .; if lim=='' then lim=40 /*assume the default for LIM? */
w= length(lim);
do j=0
Js= Js right(j, w);
end /*j*/
say 'Js=' Js /*display the list of Js to the term.*/
Line 2,144 ⟶ 3,669:
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
F: procedure expose $m. $f.; parse arg n;
M: procedure expose $m. $f.; parse arg n;
<pre>
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
Line 2,156 ⟶ 3,681:
This version is identical in function to the previous example, but it also can compute and
<br>display a specific request (indicated by a negative number for the argument).
<
/*───────────────── 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;
do j=0
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")="
if lim>0 then say 'Fs=' Fs; else say 'F('aLim")="
if lim>0 then say 'Ms=' Ms; else say 'M('aLim")="
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
F: procedure expose $m. $f.; parse arg n;
M: procedure expose $m. $f.; parse arg n;
<pre>
J(70000)= 70000
Line 2,179 ⟶ 3,705:
M(70000)= 43262
</pre>
<pre>
J(250000)= 250000
Line 2,187 ⟶ 3,713:
=={{header|Ring}}==
<
see "F sequence : "
for i = 0 to 20
Line 2,207 ⟶ 3,733:
if n != 0 mr = n - f(m(n - 1)) ok
return mr
</syntaxhighlight>
=={{header|RPL}}==
≪ IF DUP THEN DUP 1 - '''FEML MALE''' - ELSE DROP 1 END
≫ ''''FEML'''' STO ( n -- F(n) )
For M(n), here is a little variant, less readable but saving one word !
≪ IF THEN LAST DUP 1 - '''MALE FEML''' - ELSE 0 END
≫ ''''MALE'''' STO ( n -- M(n) )
{{in}}
<pre>
≪ {} 0 20 FOR n n MALE + NEXT ≫ EVAL
≪ {} 0 20 FOR n n FEML + NEXT ≫ EVAL
</pre>
{{out}}
<pre>
2: { 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12 }
1: { 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 }
</pre>
=={{header|Ruby}}==
<
n == 0 ? 1 : n - M(F(n-1))
end
Line 2,218 ⟶ 3,761:
p (Array.new(20) {|n| F(n) })
p (Array.new(20) {|n| M(n) })</
{{out}}
Line 2,227 ⟶ 3,770:
=={{header|Run BASIC}}==
<
for i = 0 to 20
print f(i);" ";
Line 2,245 ⟶ 3,788:
m = 0
if n <> 0 then m = n - f(m(n - 1))
end function</
{{out}}
<pre>F sequence:1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13
Line 2,251 ⟶ 3,794:
=={{header|Rust}}==
<
match n {
0 => 1,
Line 2,275 ⟶ 3,818:
}
println!("")
}</
{{out}}
<pre>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</pre>
=={{header|S-lang}}==
<
define f();
define m();
Line 2,303 ⟶ 3,845:
foreach $1 ([0:19])
() = printf("%d ", m($1));
() = printf("\n");</
{{out}}
<pre>1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12
Line 2,309 ⟶ 3,851:
=={{header|Sather}}==
<
f(n:INT):INT
Line 2,334 ⟶ 3,876:
end;
end;
end;</
There's no need to pre-declare F or M.
=={{header|Scala}}==
<
if (n == 0) 1 else n - M(F(n-1))
def M(n:Int):Int =
Line 2,345 ⟶ 3,887:
println((0 until 20).map(F).mkString(", "))
println((0 until 20).map(M).mkString(", "))</
{{out}}
Line 2,353 ⟶ 3,895:
=={{header|Scheme}}==
<code>define</code> declarations are automatically mutually recursive:
<
(if (= n 0) 1
(- n (M (F (- n 1))))))
Line 2,359 ⟶ 3,901:
(define (M n)
(if (= n 0) 0
(- n (F (M (- n 1))))))</
If you wanted to use a <code>let</code>-like construct to create local bindings, you would do the following. The <code>define</code> construct above is just a syntactic sugar for the following where the entire rest of the scope is used as the body.
<
(if (= n 0) 1
(- n (M (F (- n 1)))))))
Line 2,368 ⟶ 3,910:
(if (= n 0) 0
(- n (F (M (- n 1))))))))
(F 19)) # evaluates to 12</
The <code>letrec</code> indicates that the definitions can be recursive, and fact that we placed these two in the same <code>letrec</code> block makes them mutually recursive.
=={{header|Seed7}}==
<
const func integer: m (in integer: n) is forward;
Line 2,411 ⟶ 3,953:
end for;
writeln;
end func;</
{{out}}
Line 2,419 ⟶ 3,961:
</pre>
=={{header|
<syntaxhighlight lang="setl">program mutual_recursion;
print("F", [f(n) : n in [0..14]]);
print("M", [m(n) : n in [0..14]]);
proc f(n);
end proc;
proc m(n);
return {[0,0]}(n) ? n - f(m(n-1));
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>F [1 1 2 2 3 3 4 5 5 6 6 7 8 8 9]
M [0 0 1 2 2 3 4 4 5 6 6 7 7 8 9]</pre>
=={{header|Sidef}}==
<syntaxhighlight lang="ruby">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|
}</
{{out}}
<pre>1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12
Line 2,437 ⟶ 3,996:
Using block closure.
<
F := [ :n |
Line 2,459 ⟶ 4,018:
ra displayNl.
rb displayNl.</
=={{header|SNOBOL4}}==
<
f f = eq(n,0) 1 :s(return)
f = n - m(f(n - 1)) :(return)
Line 2,477 ⟶ 4,036:
i = le(i,25) i + 1 :s(L1)
output = 'M: ' s1; output = 'F: ' s2
end</
{{out}}
Line 2,485 ⟶ 4,044:
=={{header|SNUSP}}==
The program shown calculates F(3) and demonstrates simple and mutual recursion.
<
F==!/=!\?\+# | />-<-\
| \@\-@/@\===?/<#
Line 2,505 ⟶ 4,064:
| | recursion
| n-1
check for zero</
=={{header|SPL}}==
<syntaxhighlight lang="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)</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Standard ML}}==
<
| f n = n - m (f (n-1))
and m 0 = 0
| m n = n - f (m (n-1))
;</
The <code>'''fun'''</code> construct creates recursive functions, and the <code>'''and'''</code> allows a group of functions to call each other. The above is just a shortcut for the following:
<
| n => n - m (f (n-1))
and m = fn 0 => 0
| n => n - f (m (n-1))
;</
which indicates that the functions call themselves (<code>'''rec'''</code>) and each other (<code>'''and'''</code>).
{{out}}
<pre>
> val terms = List.tabulate (10, fn x => x);
val terms = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]: int list
> map f terms;
val it = [1, 1, 2, 2, 3, 3, 4, 5, 5, 6]: int list
> map m terms;
val it = [0, 0, 1, 2, 2, 3, 4, 4, 5, 6]: int list
</pre>
=={{header|Swift}}==
It just works. No special pre-declaration is necessary.
<
return n == 0 ? 1 : n - M(F(n-1))
}
Line 2,541 ⟶ 4,130:
print("\(M(i)) ")
}
println()</
=={{header|Symsyn}}==
<syntaxhighlight lang="symsyn">
F param Fn
if Fn = 0
1 R
else
(Fn-1) nm1
save Fn
call F nm1
result Fr
save Fr
call M Fr
result Mr
restore Fr
restore Fn
(Fn-Mr) R
endif
return R
M param Mn
if Mn = 0
0 R
else
(Mn-1) nm1
save Mn
call M nm1
result Mr
save Mr
call F Mr
result Fr
restore Mr
restore Mn
(Mn-Fr) R
endif
return R
start
i
if i <= 19
call F i
result res
" $s res ' '" $s
+ i
goif
endif
$s []
$s
i
if i <= 19
call M i
result res
" $s res ' '" $s
+ i
goif
endif
$s []
</syntaxhighlight>
=={{header|Tailspin}}==
<syntaxhighlight lang="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
</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|Tcl}}==
<
if { $n == 0 } { expr 0; } else {
expr {$n - [f [m [expr {$n-1}] ]]};
Line 2,564 ⟶ 4,244:
puts -nonewline " ";
}
puts ""</
=={{header|TI-89 BASIC}}==
<
Define M(n) = when(n=0, 0, n - F(M(n - 1)))</
=={{header|TXR}}==
<
(if (>= 0 n)
1
Line 2,584 ⟶ 4,264:
(each ((n (range 0 15)))
(format t "f(~s) = ~s; m(~s) = ~s\n" n (f n) n (m n)))</
<pre>$ txr mutual-recursion.txr
Line 2,607 ⟶ 4,287:
{{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.
<syntaxhighlight lang="text">LOCAL(1) ' main uses locals as well
FOR a@ = 0 TO 200 ' set the array
Line 2,637 ⟶ 4,317:
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}}
<pre>F sequence:
Line 2,645 ⟶ 4,325:
0 OK, 0:199</pre>
=={{header|UNIX Shell}}==
{{works with|Bourne Again SHell}}
<
{
local n
Line 2,678 ⟶ 4,359:
echo -n " "
done
echo</
=={{header|Ursala}}==
Line 2,692 ⟶ 4,373:
than by mutual recursion, but fixed points are useful for other things as well.)
<
#import nat
#import sol
Line 2,699 ⟶ 4,380:
F = ~&?\1! difference^/~& M+ F+ predecessor
M = ~&?\0! difference^/~& F+ M+ predecessor</
This test program applies both functions to the first
twenty natural numbers.
<
test = ^(F*,M*) iota 20</
{{out}}
<pre>
Line 2,710 ⟶ 4,391:
<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>)</pre>
=={{header|Vala}}==
<syntaxhighlight lang="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));
}
}</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|VBA}}==
<syntaxhighlight lang="vb">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</syntaxhighlight>{{out}}
<pre> 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 </pre>
=={{header|Wren}}==
<syntaxhighlight lang="wren">var F = Fn.new { |n|
if (n == 0) return 1
return n - M.call(F.call(n-1))
}
var 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()</syntaxhighlight>
{{out}}
<pre>
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
</pre>
=={{header|x86 Assembly}}==
Line 2,716 ⟶ 4,484:
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 <tt>func_f</tt> call <tt>func_m</tt>. If the function would have been in another source unit, we should have declared it <tt>extern</tt> (the linker will resolve the symbol), as done for <tt>printf</tt>.<br>
(It must be linked with the C standard library <tt>libc</tt> or similar and a startup code; lazyly a <tt>gcc mutrec.o</tt> works, being <tt>mutrec.o</tt> produced by e.g. <tt>nasm -f elf mutrec.asm</tt>)
<
extern printf
Line 2,797 ⟶ 4,565:
db 10,0
end</
=={{header|XPL0}}==
<
ffunc M; \forward-referenced function declaration
Line 2,817 ⟶ 4,585:
for I:= 0 to 19 do [IntOut(0, M(I)); ChOut(0, ^ )];
CrLf(0);
]</
{{out}}
Line 2,824 ⟶ 4,592:
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12
</pre>
=={{header|Yabasic}}==
{{trans|AWK}}
<syntaxhighlight lang="yabasic">// 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</syntaxhighlight>
=={{header|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 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}}
<pre>
|