Mutual recursion: Difference between revisions
Add ABC
Not a robot (talk | contribs) (Add APL) |
Not a robot (talk | contribs) (Add ABC) |
||
(26 intermediate revisions by 18 users not shown) | |||
Line 37:
in a recursive routine, as the code below does.
<
jmp test
;;; Implementation of F(A).
Line 104:
jmp 5 ; Tail call optimization
fpfx: db 'F: $'
mpfx: db 13,10,'M: $'</
{{out}}
Line 114:
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.
Line 162:
for i = 1 while i < 20
next results = |{ results }, { hoffstadter_sequences=>m( i ) }| ) }|, /.
</syntaxhighlight>
{{output}}
Line 170:
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 183 ⟶ 203:
(if (zp n)
0
(- n (f (m (1- n)))))))</
=={{header|Ada}}==
<
procedure Mutual_Recursion is
function M(N : Integer) return Integer;
Line 213 ⟶ 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 235 ⟶ 255:
end loop;
end Mutual_recursion;</
=={{header|Aime}}==
{{trans|C}}
<
integer M(integer n);
Line 281 ⟶ 301:
o_byte('\n');
return 0;
}</
=={{header|ALGOL 68}}==
Line 289 ⟶ 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 309 ⟶ 329:
OD;
new line(stand out)
)</
{{out}}
<pre>
Line 317 ⟶ 337:
=={{header|ALGOL W}}==
<
% define mutually recursive funtions F and M that compute the elements %
% of the Hofstadter Female and Male sequences %
Line 334 ⟶ 354:
for i := 0 until 20 do writeon( M( i ) );
end.</
=={{header|APL}}==
{{works with|Dyalog APL}}
<
m ← {⍵=0:0 ⋄ ⍵-f∇⍵-1}
⍉'nFM'⍪↑(⊢,f,m)¨0,⍳20</
{{out}}
<pre>n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Line 348 ⟶ 368:
=={{header|AppleScript}}==
<
on f(x)
if x = 0 then
Line 413 ⟶ 433:
end repeat
return lst
end range</
{{Out}}
<
{0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12}}</
=={{header|ARM Assembly}}==
Line 441 ⟶ 461:
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.
Line 506 ⟶ 526:
dstr: .ascii "\2"
dgt: .ascii "* "
nl: .ascii "\1\n"</
{{out}}
Line 514 ⟶ 534:
=={{header|Arturo}}==
<
m: $[n][ if? n=0 -> 0 else -> n-f m n-1 ]
Line 521 ⟶ 541:
print ["m(" i ")=" m i]
print ""
]</
{{out}}
Line 589 ⟶ 609:
=={{header|AutoHotkey}}==
<
i := A_Index-1, t .= "`n" i "`t " M(i) "`t " F(i)
MsgBox x`tmale`tfemale`n%t%
Line 599 ⟶ 619:
M(n) {
Return n ? n - F(M(n-1)) : 0
}</
{{trans|C}}
Line 605 ⟶ 625:
This one is an alternative to the above.
<
Return
Line 635 ⟶ 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.
<
#!/usr/local/bin/gawk -f
Line 659 ⟶ 679:
}
print ""
}</
{{out}}
Line 669 ⟶ 689:
=={{header|BaCon}}==
<
FUNCTION F(int n) TYPE int
RETURN IIF(n = 0, 1, n - M(F(n -1)))
Line 689 ⟶ 709:
PRINT M(i) FORMAT "%2d "
NEXT
PRINT</
{{out}}
Line 698 ⟶ 718:
=={{header|BASIC}}==
{{works with|QBasic}}
<
DECLARE FUNCTION m! (n!)
Line 715 ⟶ 735:
m = f(m(n - 1))
END IF
END FUNCTION</
==={{header|BBC BASIC}}===
<
PRINT "F sequence:"
FOR i% = 0 TO 20
Line 733 ⟶ 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 743 ⟶ 763:
==={{header|IS-BASIC}}===
<
110 PRINT "F sequence:"
120 FOR I=0 TO 20
Line 765 ⟶ 785:
300 LET M=N-F(M(N-1))
310 END IF
320 END DEF</
=={{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}}==
<
define f(n) {
if ( n == 0 ) return(1);
Line 778 ⟶ 820:
if ( n == 0 ) return(0);
return(n - f(m(n-1)));
}</
{{works with|GNU bc}}
Line 784 ⟶ 826:
POSIX bc doesn't have the <tt>print</tt> statement.
<
for(i=0; i < 19; i++) {
print f(i); print " ";
Line 793 ⟶ 835:
}
print "\n";
quit</
{{out}}
Line 807 ⟶ 849:
=={{header|BCPL}}==
<
// Mutually recursive functions
Line 826 ⟶ 868:
$)
writes("*N")
$)</
{{out}}
<pre>F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9
Line 832 ⟶ 874:
=={{header|BQN}}==
<
M ← {0:0; 𝕩-F M𝕩-1}
⍉"FM"∾>(F∾M)¨↕15</
{{out}}
<pre>┌─
Line 842 ⟶ 884:
=={{header|Bracmat}}==
<
(M=.!arg:0&0|!arg+-1*F$(M$(!arg+-1)));
Line 849 ⟶ 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 867 ⟶ 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 873 ⟶ 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 902 ⟶ 967:
printf("\n");
return EXIT_SUCCESS;
}</
=={{header|C sharp|C#}}==
<
class Hofstadter {
static public int F(int n) {
Line 925 ⟶ 990:
}
}
}</
=={{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 964 ⟶ 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 970 ⟶ 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 987 ⟶ 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 1,004 ⟶ 1,069:
printAll((0:20).map(f));
printAll((0:20).map(m));
}</
{{out}}
Line 1,014 ⟶ 1,079:
=={{header|Clojure}}==
<
(defn M [n]
Line 1,024 ⟶ 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 1,036 ⟶ 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 1,055 ⟶ 1,163:
(if (zerop n)
1
(- n (m (f (- n 1))))))</
=={{header|D}}==
<
int male(in int n) pure nothrow {
Line 1,071 ⟶ 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]
Line 1,077 ⟶ 1,185:
=={{header|Dart}}==
<
int F(int n) => n==0?0:n-M(F(n-1));
Line 1,088 ⟶ 1,196:
print("M: $m");
print("F: $f");
}</
=={{header|Delphi}}==
<syntaxhighlight lang="delphi">
unit Hofstadter;
Line 1,120 ⟶ 1,228:
end.
</syntaxhighlight>
=={{header|Déjà Vu}}==
<
if n:
- n M F -- n
Line 1,136 ⟶ 1,244:
for i range 0 10:
!.( M i F i )</
{{out}}
<pre>0 1
Line 1,149 ⟶ 1,257:
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}}==
<
n == 0 ? 1 : n - m(f(n-1))
}
Line 1,158 ⟶ 1,297:
n == 0 ? 0 : n - f(m(n-1))
}
print( (0..20).
print( (0..20).
=={{header|E}}==
Line 1,168 ⟶ 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>
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 1,232 ⟶ 1,395:
end
</syntaxhighlight>
{{out}}
<pre>
Line 1,241 ⟶ 1,404:
=={{header|Elena}}==
{{trans|Smalltalk}}
ELENA
<
import system'collections;
Line 1,253 ⟶ 1,416:
var rb := new ArrayList();
for(int i := 0
{
ra.append(F(i));
Line 1,261 ⟶ 1,424:
console.printLine(ra.asEnumerable());
console.printLine(rb.asEnumerable())
}</
{{out}}
<pre>
Line 1,269 ⟶ 1,432:
=={{header|Elixir}}==
<
def f(0), do: 1
def f(n), do: n - m(f(n - 1))
Line 1,277 ⟶ 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 1,286 ⟶ 1,449:
=={{header|Erlang}}==
<
-export([mutrec/0, f/1, m/1]).
Line 1,298 ⟶ 1,461:
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 1,321 ⟶ 1,484:
end function
idM = routine_id("M")</
=={{header|F_Sharp|F#}}==
<
match n with
| 0 -> 1
Line 1,332 ⟶ 1,495:
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 1,338 ⟶ 1,501:
=={{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 1,375 ⟶ 1,538:
}
}
</syntaxhighlight>
=={{header|FOCAL}}==
<
01.10 T "F(0..15)"
01.20 F X=0,15;S N=X;D 4;T %1,N
Line 1,396 ⟶ 1,559:
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)</
{{out}}
Line 1,406 ⟶ 1,569:
=={{header|Forth}}==
Forward references required for mutual recursion may be set up using DEFER.
<
: f ( n -- n )
Line 1,420 ⟶ 1,583:
' 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 1,427 ⟶ 1,590:
{{works with|Fortran|95 and later}}
<
implicit none
contains
Line 1,450 ⟶ 1,613:
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 1,470 ⟶ 1,633:
write(*,'(20I3)') ra
end program testmutrec</
=={{header|FreeBASIC}}==
<
' Need forward declaration of M as it's used
Line 1,505 ⟶ 1,668:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 1,517 ⟶ 1,680:
=={{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 1,547 ⟶ 1,769:
}
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 1,565 ⟶ 1,787:
=={{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 1,573 ⟶ 1,795:
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,588 ⟶ 1,810:
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,599 ⟶ 1,821:
M Z = Z
M (S n) = (S n) `minus` F(M(n))
}</
=={{header|Io}}==
<
m := method(n, if( n == 0, 0, n - f(m(n-1))))
Range
0 to(19) map(n,f(n)) println
0 to(19) map(n,m(n)) println</
{{out}}
<pre>list(1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12)
Line 1,613 ⟶ 1,835:
=={{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.
<
import java.util.HashMap;
import java.util.Map;
Line 1,667 ⟶ 1,889:
}
</syntaxhighlight>
{{out}}
First 20 values of the Female sequence:
Line 1,713 ⟶ 1,935:
=={{header|JavaScript}}==
<
return (num === 0) ? 1 : num - m(f(num - 1));
}
Line 1,731 ⟶ 1,953:
//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,737 ⟶ 1,959:
ES6 implementation
<
var m = num => (num === 0) ? 0 : num - f(m(num - 1));
Line 1,750 ⟶ 1,972:
//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}}==
Line 1,761 ⟶ 1,983:
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;
Line 1,767 ⟶ 1,989:
def F:
if . == 0 then 1 else . - ((. - 1) | F | M) end;</
[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}}==
<
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)); }
Line 1,794 ⟶ 2,016:
0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12
=!EXPECTEND!=
*/</
{{out}}
Line 1,805 ⟶ 2,027:
=={{header|Julia}}==
<
M(n) = n < 1 ? zero(n) : n - F(M(n - 1))</
{{out}}
<pre>
Line 1,814 ⟶ 2,036:
=={{header|Kotlin}}==
<
fun f(n: Int): Int =
Line 1,833 ⟶ 2,055:
for (i in 0..n) print("%3d".format(i))
println()
println("-".repeat(
print("F :")
for (i in 0..
println()
print("M :")
for (i in 0..
println()
}</
{{out}}
Line 1,852 ⟶ 2,074:
=={{header|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}}}} }}}
Line 1,860 ⟶ 2,082:
{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:
<
{def cache
{def cache.F {#.new}}
Line 1,900 ⟶ 2,122:
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,931 ⟶ 2,153:
end if
end function
</syntaxhighlight>
{{out}}
<pre>F sequence.
Line 1,939 ⟶ 2,161:
=={{header|LibreOffice Basic}}==
<
'// Utility functions
Line 2,033 ⟶ 2,255:
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 2,050 ⟶ 2,272:
[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 2,083 ⟶ 2,305:
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 2,089 ⟶ 2,311:
=={{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}}==
Line 2,108 ⟶ 2,330:
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
Line 2,186 ⟶ 2,408:
Checkit2
</syntaxhighlight>
{{out}}
<pre>
Line 2,195 ⟶ 2,417:
=={{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}}==
Line 2,232 ⟶ 2,454:
or <code>MREC.</code>, which are the actual recursive functions, with a dummy zero argument.
<
R SET UP STACK SPACE
Line 2,288 ⟶ 2,510:
VECTOR VALUES FMT =
0 $2HF(,I2,4H) = ,I2,S8,2HM(,I2,4H) = ,I2*$
END OF PROGRAM</
{{out}}
Line 2,315 ⟶ 2,537:
=={{header|Maple}}==
<
if (n = 0) then
return 1;
Line 2,331 ⟶ 2,553:
end proc;
seq(female_seq(i), i=0..10);
seq(male_seq(i), i=0..10);</
{{Out|Output}}
<pre>1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6
Line 2,338 ⟶ 2,560:
=={{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 2,364 ⟶ 2,586:
Fn = n - male(female(n-1));
end</
male.m:
<
if n == 0
Line 2,375 ⟶ 2,597:
Mn = n - female(male(n-1));
end</
{{out}}
<
>> arrayfun(@female,n)
Line 2,389 ⟶ 2,611:
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 2,415 ⟶ 2,637:
[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6]
remfunction(f, m)$</
=={{header|Mercury}}==
<syntaxhighlight lang="text">
:- module mutual_recursion.
:- interface.
Line 2,439 ⟶ 2,661:
m(N) = ( if N = 0 then 0 else N - f(m(N - 1)) ).
</syntaxhighlight>
=={{header|MiniScript}}==
<
if n > 0 then return n - m(f(n - 1))
return 1
Line 2,453 ⟶ 2,675:
print f(12)
print m(12)</
{{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 2,536 ⟶ 2,775:
LDA $255,NL
TRAP 0,Fputs,StdOut
TRAP 0,Halt,0</
{{out}}
Line 2,544 ⟶ 2,783:
=={{header|Modula-2}}==
<
FROM InOut IMPORT WriteCard, WriteString, WriteLn;
Line 2,581 ⟶ 2,820:
Show("F", F);
Show("M", M);
END MutualRecursion.</
{{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 2,609 ⟶ 2,848:
foreach (n in [0 .. 20]) Write("{0} ", M(n));
}
}</
=={{header|Nim}}==
<
proc f(n: int): int =
Line 2,624 ⟶ 2,863:
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}}
<
class MutualRecursion {
function : Main(args : String[]) ~ Nil {
Line 2,649 ⟶ 2,938:
}
}
</syntaxhighlight>
=={{header|Objective-C}}==
Line 2,655 ⟶ 2,944:
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 2,688 ⟶ 2,977:
printf("\n");
return 0;
}</
=={{header|OCaml}}==
<
| 0 -> 1
| n -> n - m(f(n-1))
Line 2,697 ⟶ 2,986:
| 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 2,706 ⟶ 2,995:
(The code is written to handle vectors, as the testing part shows)
<
for i = 1:length(n)
if (n(i) == 0)
Line 2,724 ⟶ 3,013:
endif
endfor
endfunction</
<
ra = F([0:19]);
rb = M([0:19]);
disp(ra);
disp(rb);</
=={{header|Oforth}}==
Line 2,736 ⟶ 3,025:
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 2,747 ⟶ 3,036:
0 20 seqFrom map(#F) println
0 20 seqFrom map(#M) println</
{{out}}
Line 2,757 ⟶ 3,046:
=={{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.
<
(letrec ((F (lambda (n)
(if (= n 0) 1
Line 2,766 ⟶ 3,055:
(print (F 19)))
; produces 12
</syntaxhighlight>
=={{header|Order}}==
Line 2,772 ⟶ 3,061:
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 2,788 ⟶ 3,077:
//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 2,805 ⟶ 3,094:
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 2,815 ⟶ 3,104:
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 2,848 ⟶ 3,137:
end;
writeln;
end.</
=={{header|Perl}}==
<
sub M { my $n = shift; $n ? $n - F(M($n-1)) : 0 }
Line 2,857 ⟶ 3,146:
foreach my $sequence (\&F, \&M) {
print join(' ', map $sequence->($_), 0 .. 19), "\n";
}</
{{out}}
<pre>
Line 2,865 ⟶ 3,154:
=={{header|Phix}}==
You should normally explicitly declare forward routines since it often makes things easier to understand (strictly
<!--<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 2,891 ⟶ 3,183:
=={{header|PHP}}==
<
function F($n)
{
Line 2,913 ⟶ 3,205:
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 2,924 ⟶ 3,284:
(if (=0 N)
0
(- N (f (m (dec N)))) ) )</
=={{header|PL/I}}==
<
M: procedure (n) returns (fixed) recursive; /* 8/1/2010 */
Line 2,946 ⟶ 3,306:
put skip list ( F(i), M(i) );
end;
end test;</
=={{header|PostScript}}==
<syntaxhighlight lang="text">
/female{
/n exch def
Line 2,967 ⟶ 3,327:
}ifelse
}def
</syntaxhighlight>
{{libheader|initlib}}
<
/F {
{
Line 2,986 ⟶ 3,346:
}.
</syntaxhighlight>
=={{header|PowerShell}}==
<
if ($n -eq 0) { return 1 }
return $n - (M (F ($n - 1)))
Line 2,997 ⟶ 3,357:
if ($n -eq 0) { return 0 }
return $n - (F (M ($n - 1)))
}</
=={{header|Prolog}}==
<
female(N,F) :- N>0,
N1 is N-1,
Line 3,012 ⟶ 3,372:
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 3,030 ⟶ 3,390:
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 3,082 ⟶ 3,442:
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 3,089 ⟶ 3,449:
=={{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 3,105 ⟶ 3,465:
See also [http://rosettacode.org/wiki/Even_or_odd#Quackery:_With_Anonymous_Mutual_Recursion Even or Odd#Quackery: With Anonymous Mutual recursion].
<
[ dup 0 = if done
Line 3,117 ⟶ 3,477:
20 times [ i^ f echo sp ] cr
say "m = "
20 times [ i^ m echo sp ] cr</
{{out}}
Line 3,125 ⟶ 3,485:
=={{header|R}}==
<
M <- function(n) ifelse(n == 0, 0, n - F(M(n-1)))</
<
print.table(lapply(0:19, F))</
=={{header|Racket}}==
<
(define (F n)
(if (>= 0 n)
Line 3,141 ⟶ 3,501:
(if (>= 0 n)
0
(- n (F (M (sub1 n))))))</
=={{header|Raku}}==
(formerly Perl 6)
A direct translation of the definitions of <math>F</math> and <math>M</math>:
<syntaxhighlight lang="raku"
multi F(\𝑛) { 𝑛 - M(F(𝑛 - 1)) }
multi M(\𝑛) { 𝑛 - F(M(𝑛 - 1)) }
say map &F, ^20;
say map &M, ^20;</
{{out}}
<pre>
Line 3,159 ⟶ 3,519:
=={{header|REBOL}}==
<
Title: "Mutual Recursion"
URL: http://rosettacode.org/wiki/Mutual_Recursion
Line 3,176 ⟶ 3,536:
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 3,182 ⟶ 3,542:
<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>>
<Prout 'M: ' <S M 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 .; if lim='' then lim= 40; w= length(lim); pad= left('', 20)
Line 3,195 ⟶ 3,573:
/*──────────────────────────────────────────────────────────────────────────────────────*/
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) )</
{{out|output|text= when using the default input of: <tt> 40 </tt>}}
Line 3,246 ⟶ 3,624:
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); $m.=.; $m.0= 0; $f.=.; $f.0= 1; Js=; Fs=; Ms=
Line 3,259 ⟶ 3,637:
/*──────────────────────────────────────────────────────────────────────────────────────*/
F: procedure expose $m. $f.; parse arg n; if $f.n==. then $f.n= n-M(F(n-1)); return $f.n
M: procedure expose $m. $f.; parse arg n; if $m.n==. then $m.n= n-F(M(n-1)); return $m.n</
{{out|output|text= when using the default input of: <tt> 99 </tt>}}
<pre>
Line 3,270 ⟶ 3,648:
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.*/
Line 3,287 ⟶ 3,665:
/*──────────────────────────────────────────────────────────────────────────────────────*/
F: procedure expose $m. $f.; parse arg n; if $f.n==. then $f.n= n-M(F(n-1)); return $f.n
M: procedure expose $m. $f.; parse arg n; if $m.n==. then $m.n= n-F(M(n-1)); return $m.n</
{{out|output|text= when using the input of: <tt> -70000 </tt>}}
<pre>
Line 3,302 ⟶ 3,680:
=={{header|Ring}}==
<
see "F sequence : "
for i = 0 to 20
Line 3,322 ⟶ 3,700:
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 3,333 ⟶ 3,728:
p (Array.new(20) {|n| F(n) })
p (Array.new(20) {|n| M(n) })</
{{out}}
Line 3,342 ⟶ 3,737:
=={{header|Run BASIC}}==
<
for i = 0 to 20
print f(i);" ";
Line 3,360 ⟶ 3,755:
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 3,366 ⟶ 3,761:
=={{header|Rust}}==
<
match n {
0 => 1,
Line 3,390 ⟶ 3,785:
}
println!("")
}</
{{out}}
<pre>1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12
Line 3,396 ⟶ 3,791:
=={{header|S-lang}}==
<
define f();
define m();
Line 3,417 ⟶ 3,812:
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 3,423 ⟶ 3,818:
=={{header|Sather}}==
<
f(n:INT):INT
Line 3,448 ⟶ 3,843:
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 3,459 ⟶ 3,854:
println((0 until 20).map(F).mkString(", "))
println((0 until 20).map(M).mkString(", "))</
{{out}}
Line 3,467 ⟶ 3,862:
=={{header|Scheme}}==
<code>define</code> declarations are automatically mutually recursive:
<
(if (= n 0) 1
(- n (M (F (- n 1))))))
Line 3,473 ⟶ 3,868:
(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 3,482 ⟶ 3,877:
(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 3,525 ⟶ 3,920:
end for;
writeln;
end func;</
{{out}}
Line 3,532 ⟶ 3,927:
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12
</pre>
=={{header|SETL}}==
<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);
return {[0,1]}(n) ? n - m(f(n-1));
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}}==
<
func M(){}
Line 3,542 ⟶ 3,954:
[F, M].each { |seq|
{|i| seq.call(i)}.map(^20).join(' ').say
}</
{{out}}
<pre>1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12
Line 3,551 ⟶ 3,963:
Using block closure.
<
F := [ :n |
Line 3,573 ⟶ 3,985:
ra displayNl.
rb displayNl.</
=={{header|SNOBOL4}}==
<
f f = eq(n,0) 1 :s(return)
f = n - m(f(n - 1)) :(return)
Line 3,591 ⟶ 4,003:
i = le(i,25) i + 1 :s(L1)
output = 'M: ' s1; output = 'F: ' s2
end</
{{out}}
Line 3,599 ⟶ 4,011:
=={{header|SNUSP}}==
The program shown calculates F(3) and demonstrates simple and mutual recursion.
<
F==!/=!\?\+# | />-<-\
| \@\-@/@\===?/<#
Line 3,619 ⟶ 4,031:
| | recursion
| n-1
check for zero</
=={{header|SPL}}==
<
? n=0, <= 1
<= n-m(f(n-1))
Line 3,635 ⟶ 4,047:
<
#.output("F:",fs)
#.output("M:",ms)</
{{out}}
<pre>
Line 3,643 ⟶ 4,055:
=={{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>).
Line 3,670 ⟶ 4,082:
=={{header|Swift}}==
It just works. No special pre-declaration is necessary.
<
return n == 0 ? 1 : n - M(F(n-1))
}
Line 3,685 ⟶ 4,097:
print("\(M(i)) ")
}
println()</
=={{header|Symsyn}}==
<syntaxhighlight lang="symsyn">
F param Fn
if Fn = 0
Line 3,745 ⟶ 4,157:
endif
$s []
</syntaxhighlight>
=={{header|Tailspin}}==
<
templates male
when <=0> do 0 !
Line 3,762 ⟶ 4,174:
0..10 -> 'M$;: $->male; F$;: $->female;
' -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 3,779 ⟶ 4,191:
=={{header|Tcl}}==
<
if { $n == 0 } { expr 0; } else {
expr {$n - [f [m [expr {$n-1}] ]]};
Line 3,799 ⟶ 4,211:
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 3,819 ⟶ 4,231:
(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 3,842 ⟶ 4,254:
{{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 3,872 ⟶ 4,284:
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 3,883 ⟶ 4,295:
=={{header|UNIX Shell}}==
{{works with|Bourne Again SHell}}
<
{
local n
Line 3,914 ⟶ 4,326:
echo -n " "
done
echo</
=={{header|Ursala}}==
Line 3,928 ⟶ 4,340:
than by mutual recursion, but fixed points are useful for other things as well.)
<
#import nat
#import sol
Line 3,935 ⟶ 4,347:
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 3,948 ⟶ 4,360:
=={{header|Vala}}==
<
if (n == 0) return 1;
return n - M(F(n - 1));
Line 3,972 ⟶ 4,384:
print("%2d ", M(s));
}
}</
{{out}}
<pre>
Line 3,982 ⟶ 4,394:
=={{header|VBA}}==
<
If n = 0 Then
F = 1
Line 4,007 ⟶ 4,419:
Debug.Print M(i);
Next i
End Sub</
<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))
Line 4,028 ⟶ 4,438:
System.write("\nM(0..20): ")
(0..20).each { |i| System.write("%(M.call(i)) ") }
System.print()</
{{out}}
Line 4,041 ⟶ 4,451:
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 4,122 ⟶ 4,532:
db 10,0
end</
=={{header|XPL0}}==
<
ffunc M; \forward-referenced function declaration
Line 4,142 ⟶ 4,552:
for I:= 0 to 19 do [IntOut(0, M(I)); ChOut(0, ^ )];
CrLf(0);
]</
{{out}}
Line 4,152 ⟶ 4,562:
=={{header|Yabasic}}==
{{trans|AWK}}
<
sub F(n)
if n = 0 return 1
Line 4,172 ⟶ 4,582:
print M(i) using "###";
next
print</
=={{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>
|