Mutual recursion: Difference between revisions

in a recursive routine, as the code below does.

 

jmp test

;;; Implementation of F(A).

jmp 5 ; Tail call optimization

fpfx: db 'F: $'

 

{{out}}

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

 

report z_mutual_recursion.

 

for i = 1 while i < 20

next results = |{ results }, { hoffstadter_sequences=>m( i ) }| ) }|, /.

 

{{output}}

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|ACL2}}==

(defun f (n)

(declare (xargs :mode :program))

(if (zp n)

0

 

=={{header|Ada}}==

procedure Mutual_Recursion is

function M(N : Integer) return Integer;

Put_Line(Integer'Image(M(I)));

end loop;

 

{{Works with|Ada 2012}}

procedure Mutual_Recursion is

function M(N: Natural) return Natural;

end loop;

 

=={{header|Aime}}==

{{trans|C}}

 

integer M(integer n);

 

o_byte('\n');

return 0;

 

=={{header|ALGOL 68}}==

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

OD;

new line(stand out)

{{out}}

<pre>

 

=={{header|ALGOL W}}==

% define mutually recursive funtions F and M that compute the elements %

% of the Hofstadter Female and Male sequences %

for i := 0 until 20 do writeon( M( i ) );

 

 

=={{header|APL}}==

{{works with|Dyalog APL}}

m ← {⍵=0:0 ⋄ ⍵-f∇⍵-1}

{{out}}

<pre>n 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

=={{header|AppleScript}}==

 

on f(x)

if x = 0 then

end repeat

return lst

 

{{Out}}

 

=={{header|ARM Assembly}}==

the link register must be saved by hand (as the code below shows several ways of doing).

 

.global _start

@@@ Implementation of F(n), n in R0. n is considered unsigned.

dstr: .ascii "\2"

dgt: .ascii "* "

 

{{out}}

 

=={{header|Arturo}}==

m: $[n][ if? n=0 -> 0 else -> n-f m n-1 ]

print ["m(" i ")=" m i]

print ""

 

{{out}}

 

=={{header|AutoHotkey}}==

i := A_Index-1, t .= "`n" i "`t " M(i) "`t " F(i)

MsgBox x`tmale`tfemale`n%t%

M(n) {

Return n ? n - F(M(n-1)) : 0

 

{{trans|C}}

This one is an alternative to the above.

 

Return

 

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

 

}

print ""

 

{{out}}

 

=={{header|BaCon}}==

FUNCTION F(int n) TYPE int

RETURN IIF(n = 0, 1, n - M(F(n -1)))

PRINT M(i) FORMAT "%2d "

NEXT

 

{{out}}

=={{header|BASIC}}==

{{works with|QBasic}}

DECLARE FUNCTION m! (n!)

 

m = f(m(n - 1))

END IF

 

==={{header|BBC BASIC}}===

PRINT "F sequence:"

FOR i% = 0 TO 20

DEF FNf(n%) IF n% = 0 THEN = 1 ELSE = n% - FNm(FNf(n% - 1))

{{out}}

<pre>

 

==={{header|IS-BASIC}}===

110 PRINT "F sequence:"

120 FOR I=0 TO 20

300 LET M=N-F(M(N-1))

310 END IF

 

=={{header|Bc}}==

 

define f(n) {

if ( n == 0 ) return(1);

if ( n == 0 ) return(0);

return(n - f(m(n-1)));

 

{{works with|GNU bc}}

POSIX bc doesn't have the <tt>print</tt> statement.

 

for(i=0; i < 19; i++) {

print f(i); print " ";

}

print "\n";

 

{{out}}

 

=={{header|BCPL}}==

 

// Mutually recursive functions

$)

writes("*N")

{{out}}

<pre>F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9

 

=={{header|BQN}}==

M ← {0:0; 𝕩-F M𝕩-1}

{{out}}

<pre>┌─

 

=={{header|Bracmat}}==

(M=.!arg:0&0|!arg+-1*F$(M$(!arg+-1)));

 

 

-1:?n&whl'(!n+1:~>20:?n&put$(M$!n " "))&put$\n

 

=={{header|Brat}}==

 

male = { n |

 

p 0.to(20).map! { n | female n }

 

=={{header|C}}==

To let C see functions that will be used, it is enough to declare them. Normally this is done in a header file; in this example we do it directly in the code. If we do not declare them explicitly, they get an implicit declaration (if implicit declaration matches the use, everything's fine; but it is better however to write an explicit declaration)

 

#include <stdlib.h>

 

printf("\n");

return EXIT_SUCCESS;

 

=={{header|C sharp|C#}}==

class Hofstadter {

static public int F(int n) {

}

}

 

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

cout << endl;

return 0;

 

The following version shows better what's going on and why we ''seemingly'' didn't need pre-declaration (like C) when "encapsulating" the functions as static (class) methods.

This version is equivalent to the above but does not inline the definition of the methods into the definition of the class. Here the method declarations in the class definition serves as the "pre-declaration" for the methods, as in C.

 

{

public:

if ( n == 0 ) return 0;

return n - F(M(n-1));

 

=={{header|Ceylon}}==

 

=> if (n > 0)

then n - m(f(n-1))

printAll((0:20).map(f));

printAll((0:20).map(m));

 

{{out}}

=={{header|Clojure}}==

 

 

(defn M [n]

(if (zero? n)

1

 

=={{header|CLU}}==

 

% Print the first few values for F and M

po: stream := stream$primary_output()

stream$puts(po, name || ":")

stream$puts(po, " " || int$unparse(fn(i)))

stream$putl(po, "")

 

{{out}}

<pre>F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9

 

=={{header|CoffeeScript}}==

F = (n) ->

if n is 0 then 1 else n - M F n - 1

console.log [0...20].map F

console.log [0...20].map M

 

{{out}}

> coffee mutual_recurse.coffee

[ 1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12 ]

[ 0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12 ]

 

=={{header|Common Lisp}}==

 

(if (zerop n)

0

(if (zerop n)

1

 

=={{header|D}}==

 

int male(in int n) pure nothrow {

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]

 

=={{header|Dart}}==

int F(int n) => n==0?0:n-M(F(n-1));

 

print("M: $m");

print("F: $f");

 

=={{header|Delphi}}==

unit Hofstadter;

 

 

end.

 

=={{header|Déjà Vu}}==

if n:

- n M F -- n

 

for i range 0 10:

{{out}}

<pre>0 1

 

=={{header|Draco}}==

* This is done using 'extern', same as if it had been in a

* different compilation unit. */

for i from 0 upto 15 do write(M(i):2) od;

writeln()

{{out}}

<pre>F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9

=={{header|Dyalect}}==

 

n == 0 ? 1 : n - m(f(n-1))

}

n == 0 ? 0 : n - f(m(n-1))

}

 

=={{header|E}}==

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

 

<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|Eiffel}}==

class

APPLICATION

 

end

{{out}}

<pre>

=={{header|Elena}}==

{{trans|Smalltalk}}

import system'collections;

var rb := new ArrayList();

{

ra.append(F(i));

console.printLine(ra.asEnumerable());

console.printLine(rb.asEnumerable())

{{out}}

<pre>

 

=={{header|Elixir}}==

def f(0), do: 1

def f(n), do: n - m(f(n - 1))

 

IO.inspect Enum.map(0..19, fn n -> MutualRecursion.f(n) end)

 

{{out}}

 

=={{header|Erlang}}==

-export([mutrec/0, f/1, m/1]).

 

io:format("~n", []),

lists:map(fun(X) -> io:format("~w ", [m(X)]) end, lists:seq(0,19)),

 

=={{header|Euphoria}}==

 

function F(integer n)

end function

 

 

=={{header|F_Sharp|F#}}==

 

match n with

| 0 -> 1

match n with

| 0 -> 0

 

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

=={{header|Factor}}==

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

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

 

=={{header|FALSE}}==

[$[$1-m;!f;!- ]? ]m:

[0[$20\>][\$@$@!." "1+]#%%]t:

f; t;!"

 

=={{header|Fantom}}==

 

class Main

{

}

}

 

=={{header|FOCAL}}==

01.10 T "F(0..15)"

01.20 F X=0,15;S N=X;D 4;T %1,N

05.11 R

05.20 S D=D+1;S N(D)=N(D-1)-1;D 5;D 4

 

{{out}}

=={{header|Forth}}==

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

 

: f ( n -- n )

 

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

 

=={{header|Fortran}}==

 

{{works with|Fortran|95 and later}}

implicit none

contains

end function f

 

 

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

 

use MutualRec

implicit none

write(*,'(20I3)') ra

 

=={{header|FreeBASIC}}==

 

' Need forward declaration of M as it's used

Print

Print "Press any key to quit"

 

{{out}}

=={{header|Fōrmulæ}}==

 

 

 

 

=={{header|Go}}==

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

import "fmt"

 

}

fmt.Println()

 

=={{header|Groovy}}==

Solution:

f = { n -> n == 0 ? 1 : n - m(f(n-1)) }

 

Test program:

 

{{out}}

=={{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)

 

main = do

print $ map f [0..19]

 

=={{header|Icon}} and {{header|Unicon}}==

every write(F(!arglist)) # F of all arguments

end

if integer(n) >= 0 then

return (0 = n) | n - F(M(n-1))

 

=={{header|Idris}}==

F : Nat -> Nat

F Z = (S Z)

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

{{out}}

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

 

=={{header|J}}==

 

Example use:

 

 

 

=={{header|Java}}==

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

import java.util.HashMap;

import java.util.Map;

 

}

{{out}}

First 20 values of the Female sequence:

 

=={{header|JavaScript}}==

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

}

//return a new array of the results and join with commas to print

console.log(a.map(function (n) { return f(n); }).join(', '));

{{out}}

<pre>1,1,2,2,3,3,4,5,5,6,6,7,8,8,9,9,10,11,11,12

 

ES6 implementation

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

 

//return a new array of the results and join with commas to print

console.log(a.map(n => f(n)).join(', '));

 

More ES6 implementation

 

 

=={{header|jq}}==

 

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

def M:

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

 

def F:

[range(0;20) | F],

 

[1,1,2,2,3,3,4,5,5,6,6,7,8,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)); }

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

=!EXPECTEND!=

 

{{out}}

 

=={{header|Julia}}==

{{out}}

<pre>

 

=={{header|Kotlin}}==

 

fun f(n: Int): Int =

for (i in 0..n) print("%3d".format(i))

println()

println()

println()

 

{{out}}

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

{map M {serie 0 19}}

-> 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12

 

The naïve version is very slow, {F 80} requires 3800 ms on a recent laptop, so let's memoize:

 

{def cache

{def cache.F {#.new}}

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

 

=={{header|Liberty BASIC}}==

print "F sequence."

for i = 0 to 20

end if

end function

{{out}}

<pre>F sequence.

 

=={{header|LibreOffice Basic}}==

 

'// Utility functions

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

 

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

[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 ?] []

 

=={{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) {

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

 

=={{header|Lua}}==

function m(n) return n > 0 and n - f(m(n-1)) or 0 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

 

=={{header|M2000 Interpreter}}==

 

Last module export to clipboard and that used for output here.

\\ set console 70 characters by 40 lines

Form 70, 40

Checkit2

 

{{out}}

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

 

=={{header|MAD}}==

or <code>MREC.</code>, which are the actual recursive functions, with a dummy zero argument.

 

R SET UP STACK SPACE

VECTOR VALUES FMT =

0 $2HF(,I2,4H) = ,I2,S8,2HM(,I2,4H) = ,I2*$

 

{{out}}

 

=={{header|Maple}}==

if (n = 0) then

return 1;

end proc;

seq(female_seq(i), i=0..10);

{{Out|Output}}

<pre>1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6

=={{header|Mathematica}}/{{header|Wolfram Language}}==

Without caching:

m[0]:=0

f[n_]:=n-m[f[n-1]]

With caching:

m[0]:=0

f[n_]:=f[n]=n-m[f[n-1]]

Example finding f(1) to f(30) and m(1) to m(30):

gives back:

 

=={{header|MATLAB}}==

female.m:

 

if n == 0

Fn = n - male(female(n-1));

 

male.m:

if n == 0

Mn = n - female(male(n-1));

 

{{out}}

>> arrayfun(@female,n)

 

ans =

 

 

=={{header|Maxima}}==

 

m[0]: 0$

f[n] := n - m[f[n - 1]]$

[0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6]

 

 

=={{header|Mercury}}==

:- module mutual_recursion.

:- interface.

 

m(N) = ( if N = 0 then 0 else N - f(m(N - 1)) ).

 

=={{header|MiniScript}}==

if n > 0 then return n - m(f(n - 1))

return 1

 

print f(12)

{{out}}

<pre>8

7</pre>

 

=={{header|MMIX}}==

 

GREG @

LDA $255,NL

TRAP 0,Fputs,StdOut

 

{{out}}

 

=={{header|Modula-2}}==

FROM InOut IMPORT WriteCard, WriteString, WriteLn;

 

Show("F", F);

Show("M", M);

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

 

foreach (n in [0 .. 20]) Write("{0} ", M(n));

}

 

=={{header|Nim}}==

 

proc f(n: int): int =

for i in 1 .. 10:

echo f(i)

 

=={{header|Objeck}}==

{{trans|C}}

 

class MutualRecursion {

function : Main(args : String[]) ~ Nil {

}

}

 

=={{header|Objective-C}}==

Objective-C has prior declaration rules similar to those stated above for [[Mutual Recursion#C|C]], for C-like types. In this example we show the use of a two class method; this works since we need an <tt>interface</tt> block that is like declaration of functions in C code.

 

 

@interface Hofstadter : NSObject

printf("\n");

return 0;

 

=={{header|OCaml}}==

| 0 -> 1

| n -> n - m(f(n-1))

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

(The code is written to handle vectors, as the testing part shows)

 

for i = 1:length(n)

if (n(i) == 0)

endif

endfor

 

ra = F([0:19]);

rb = M([0:19]);

disp(ra);

 

=={{header|Oforth}}==

Oforth can declare methods objects without any implementation. This allows to implement mutual recursion. This does not work with functions (declaration and implementation must be together).

 

 

Integer method: F

 

0 20 seqFrom map(#F) println

 

{{out}}

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

(print (F 19)))

; produces 12

 

=={{header|Order}}==

Since Order is powered by the C preprocessor, definitions follow the same rule as CPP macros: they can appear in any order relative to each other as long as all are defined before the ORDER_PP block that calls them.

 

 

#define ORDER_PP_DEF_8f \

//Test

ORDER_PP(8for_each_in_range(8fn(8N, 8print(8f(8N))), 0, 19))

 

=={{header|Oz}}==

fun {F N}

if N == 0 then 1

in

{Show {Map {List.number 0 9 1} F}}

 

=={{header|PARI/GP}}==

 

=={{header|Pascal}}==

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}

end;

writeln;

 

=={{header|Perl}}==

sub M { my $n = shift; $n ? $n - F(M($n-1)) : 0 }

 

foreach my $sequence (\&F, \&M) {

print join(' ', map $sequence->($_), 0 .. 19), "\n";

{{out}}

<pre>

 

=={{header|Phix}}==

{{out}}

<pre>

=={{header|PHP}}==

 

function F($n)

{

echo implode(" ", $ra) . "\n";

echo implode(" ", $rb) . "\n";

 

=={{header|PicoLisp}}==

(if (=0 N)

1

(if (=0 N)

0

 

=={{header|PL/I}}==

 

M: procedure (n) returns (fixed) recursive; /* 8/1/2010 */

put skip list ( F(i), M(i) );

end;

 

=={{header|PostScript}}==

/female{

/n exch def

}ifelse

}def

 

{{libheader|initlib}}

 

/F {

{

}.

 

 

=={{header|PowerShell}}==

if ($n -eq 0) { return 1 }

return $n - (M (F ($n - 1)))

if ($n -eq 0) { return 0 }

return $n - (F (M ($n - 1)))

 

=={{header|Prolog}}==

female(N,F) :- N>0,

N1 is N-1,

male(N1,R),

female(R, R1),

 

{{works with|GNU Prolog}}

 

'''Testing'''

The Pure definitions very closely maps to the mathematical definitions.

 

M 0 = 0;

F n = n - M(F(n-1)) if n>0;

 

[1,1,2,2,3,3,4,5,5,6,6]

> let males = map M (0..10); males;

 

=={{header|PureBasic}}==

 

Procedure F(n)

Input()

CloseConsole()

{{out}}

<pre>1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12

=={{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) ])

 

{{out}}

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

20 times [ i^ f echo sp ] cr

say "m = "

 

{{out}}

 

=={{header|R}}==

 

 

=={{header|Racket}}==

(define (F n)

(if (>= 0 n)

(if (>= 0 n)

0

 

=={{header|Raku}}==

(formerly Perl 6)

A direct translation of the definitions of <math>F</math> and <math>M</math>:

multi F(\𝑛) { 𝑛 - M(F(𝑛 - 1)) }

multi M(\𝑛) { 𝑛 - F(M(𝑛 - 1)) }

 

say map &F, ^20;

{{out}}

<pre>

 

=={{header|REBOL}}==

Title: "Mutual Recursion"

URL: http://rosettacode.org/wiki/Mutual_Recursion

 

fs: [] ms: [] for i 0 19 1 [append fs f i append ms m i]

 

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

===vanilla===

This version uses vertical formatting of the output.

parse arg lim .; if lim='' then lim= 40; w= length(lim); pad= left('', 20)

 

/*──────────────────────────────────────────────────────────────────────────────────────*/

F: procedure; parse arg n; if n==0 then return 1; return n - M( F(n-1) )

{{out|output|text=&nbsp; when using the default input of: &nbsp; &nbsp; <tt> 40 </tt>}}

 

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=

/*──────────────────────────────────────────────────────────────────────────────────────*/

F: procedure expose $m. $f.; parse arg n; if $f.n==. then $f.n= n-M(F(n-1)); return $f.n

{{out|output|text=&nbsp; when using the default input of: &nbsp; &nbsp; <tt> 99 </tt>}}

<pre>

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.*/

 

/*──────────────────────────────────────────────────────────────────────────────────────*/

F: procedure expose $m. $f.; parse arg n; if $f.n==. then $f.n= n-M(F(n-1)); return $f.n

{{out|output|text=&nbsp; when using the input of: &nbsp; &nbsp; <tt> -70000 </tt>}}

<pre>

 

=={{header|Ring}}==

see "F sequence : "

for i = 0 to 20

if n != 0 mr = n - f(m(n - 1)) ok

return mr

 

=={{header|Ruby}}==

n == 0 ? 1 : n - M(F(n-1))

end

 

p (Array.new(20) {|n| F(n) })

 

{{out}}

 

=={{header|Run BASIC}}==

for i = 0 to 20

print f(i);" ";

m = 0

if n <> 0 then m = n - f(m(n - 1))

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

 

=={{header|Rust}}==

match n {

0 => 1,

}

println!("")

{{out}}

<pre>1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12

 

=={{header|S-lang}}==

define f();

define m();

foreach $1 ([0:19])

() = printf("%d ", m($1));

{{out}}

<pre>1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12

 

=={{header|Sather}}==

 

f(n:INT):INT

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 =

 

println((0 until 20).map(F).mkString(", "))

 

{{out}}

=={{header|Scheme}}==

<code>define</code> declarations are automatically mutually recursive:

(if (= n 0) 1

(- n (M (F (- n 1))))))

(define (M n)

(if (= n 0) 0

 

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

(if (= n 0) 0

(- n (F (M (- n 1))))))))

 

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;

end for;

writeln;

 

{{out}}

0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12

</pre>

 

=={{header|Sidef}}==

func M(){}

 

[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

Using block closure.

 

 

F := [ :n |

 

ra displayNl.

 

=={{header|SNOBOL4}}==

 

f f = eq(n,0) 1 :s(return)

f = n - m(f(n - 1)) :(return)

i = le(i,25) i + 1 :s(L1)

output = 'M: ' s1; output = 'F: ' s2

 

{{out}}

=={{header|SNUSP}}==

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

F==!/=!\?\+# | />-<-\

| \@\-@/@\===?/<#

| | recursion

| n-1

 

=={{header|SPL}}==

? n=0, <= 1

<= n-m(f(n-1))

<

#.output("F:",fs)

{{out}}

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

=={{header|Swift}}==

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

return n == 0 ? 1 : n - M(F(n-1))

}

print("\(M(i)) ")

}

 

=={{header|Symsyn}}==

F param Fn

if Fn = 0

endif

$s []

=={{header|Tailspin}}==

templates male

when <=0> do 0 !

0..10 -> 'M$;: $->male; F$;: $->female;

' -> !OUT::write

{{out}}

<pre>

 

=={{header|Tcl}}==

if { $n == 0 } { expr 0; } else {

expr {$n - [f [m [expr {$n-1}] ]]};

puts -nonewline " ";

}

 

=={{header|TI-89 BASIC}}==

 

 

=={{header|TXR}}==

 

(if (>= 0 n)

1

 

(each ((n (range 0 15)))

 

<pre>$ txr mutual-recursion.txr

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

 

FOR a@ = 0 TO 200 ' set the array

IF a@ = 0 THEN RETURN (0) ' memoize the solution

IF @(a@+100) < 0 THEN @(a@+100) = a@ - FUNC(_f(FUNC(_m(a@ - 1))))

{{out}}

<pre>F sequence:

=={{header|UNIX Shell}}==

{{works with|Bourne Again SHell}}

{

local n

echo -n " "

done

 

=={{header|Ursala}}==

than by mutual recursion, but fixed points are useful for other things as well.)

 

#import nat

#import sol

 

F = ~&?\1! difference^/~& M+ F+ predecessor

This test program applies both functions to the first

twenty natural numbers.

 

{{out}}

<pre>

 

=={{header|Vala}}==

if (n == 0) return 1;

return n - M(F(n - 1));

print("%2d ", M(s));

}

{{out}}

<pre>

 

=={{header|VBA}}==

If n = 0 Then

F = 1

Debug.Print M(i);

Next i

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

if (n == 0) return 1

return n - M.call(F.call(n-1))

}

 

if (n == 0) return 0

return n - F.call(M.call(n-1))

System.write("\nM(0..20): ")

(0..20).each { |i| System.write("%(M.call(i)) ") }

 

{{out}}

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

 

db 10,0

 

 

=={{header|XPL0}}==

 

ffunc M; \forward-referenced function declaration

for I:= 0 to 19 do [IntOut(0, M(I)); ChOut(0, ^ )];

CrLf(0);

 

{{out}}

=={{header|Yabasic}}==

{{trans|AWK}}

sub F(n)

if n = 0 return 1

print M(i) using "###";

next

 

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

{{out}}

<pre>