Mutual recursion: Difference between revisions

From Rosetta Code
Content added Content deleted
m (typo)
(added swift)
Line 2,089: Line 2,089:


which indicates that the functions call themselves (<code>'''rec'''</code>) and each other (<code>'''and'''</code>).
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.
<lang swift>func F(n: Int) -> Int {
return n == 0 ? 1 : n - M(F(n-1))
}

func M(n: Int) -> Int {
return n == 0 ? 0 : n - F(M(n-1))
}

for i in 0..20 {
print("\(F(i)) ")
}
println()
for i in 0..20 {
print("\(M(i)) ")
}
println()</lang>


=={{header|Tcl}}==
=={{header|Tcl}}==

Revision as of 00:21, 11 June 2014

Task
Mutual recursion
You are encouraged to solve this task according to the task description, using any language you may know.

Two functions are said to be mutually recursive if the first calls the second, and in turn the second calls the first.

Write two mutually recursive functions that compute members of the Hofstadter Female and Male sequences defined as:


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

ACL2

<lang lisp>(mutual-recursion 

(defun f (n)
   (declare (xargs :mode :program))
   (if (zp n)
       1
       (- n (m (f (1- n))))))

(defun m (n)
   (declare (xargs :mode :program))
   (if (zp n)
       0
       (- n (f (m (1- n)))))))</lang>

Ada

<lang Ada>with Ada.Text_Io; use Ada.Text_Io; procedure Mutual_Recursion is 

  function M(N : Integer) return Integer;
  function F(N : Integer) return Integer is
  begin
     if N = 0 then
        return 1;
     else
        return N - M(F(N - 1));
     end if;
  end F;
  function M(N : Integer) return Integer is
  begin
     if N = 0 then
        return 0;
     else
        return N - F(M(N-1));
     end if;
  end M;

begin 

  for I in 0..19 loop
     Put_Line(Integer'Image(F(I)));
  end loop;
  New_Line;
  for I in 0..19 loop
     Put_Line(Integer'Image(M(I)));
  end loop;

end Mutual_recursion;</lang>

Works with: Ada 2012

<lang ada>with Ada.Text_Io; use Ada.Text_Io; procedure Mutual_Recursion is 

  function M(N: Natural) return Natural;
  function F(N: Natural) return Natural;

  function M(N: Natural) return Natural is
      (if N = 0 then 0 else N – F(M(N–1)));

  function F(N: Natural) return Natural is
      (if N =0 then 1 else N – M(F(N–1)));

begin 

  for I in 0..19 loop
     Put_Line(Integer'Image(F(I)));
  end loop;
  New_Line;
  for I in 0..19 loop
     Put_Line(Integer'Image(M(I)));
  end loop;

end Mutual_recursion;</lang>

Aime

Translation of: C

<lang aime>integer F(integer n); integer M(integer n);

integer F(integer n) { 

   integer r;
   if (n) {

r = n - M(F(n - 1)); 

   } else {

r = 1; 

   }
   return r;

}

integer M(integer n) { 

   integer r;
   if (n) {

r = n - F(M(n - 1)); 

   } else {

r = 0; 

   }
   return r;

}

integer main(void) { 

   integer i;
   i = 0;
   while (i < 20) {

o_winteger(3, F(i)); i += 1; 

   }
   o_byte('\n');
   i = 0;
   while (i < 20) {

o_winteger(3, M(i)); i += 1; 

   }
   o_byte('\n');
   return 0;

}</lang>

ALGOL 68

Translation of: C
Works with: ALGOL 68 version Standard - no extensions to language used
Works with: ALGOL 68G version Any - tested with release mk15-0.8b.fc9.i386
Works with: ELLA ALGOL 68 version Any (with appropriate job cards) - tested with release 1.8.8d.fc9.i386

<lang algol68>PROC (INT)INT m; # ONLY required for ELLA ALGOL 68RS - an official subset OF full ALGOL 68 #

PROC f = (INT n)INT: 

 IF n = 0 THEN 1
 ELSE n - m(f(n-1)) FI;

m := (INT n)INT: 

 IF n = 0 THEN 0
 ELSE n - f(m(n-1)) FI;

main: ( 

 FOR i FROM 0 TO 19 DO
   print(whole(f(i),-3))
 OD;
 new line(stand out);
 FOR i FROM 0 TO 19 DO
   print(whole(m(i),-3))
 OD;
 new line(stand out)

)</lang> Output: 

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

AutoHotkey

<lang AutoHotkey>Loop 20 

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

MsgBox x`tmale`tfemale`n%t%

F(n) { 

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

}

M(n) { 

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

}</lang>

Translation of: C

This one is an alternative to the above.

<lang AutoHotkey>main() Return

F(n) { 

 If (n == 0) 
   Return 1
 Else
   Return n - M(F(n-1))

}

M(n) { 

 If (n == 0)
   Return 0
 Else
   Return n - F(M(n-1)) ;

}

main() { 

 i = 0
 While, i < 20
 {
   male .= M(i) . "`n" 
   female .= F(i) . "`n"
   i++
 }
 MsgBox % "male:`n" . male
 MsgBox % "female:`n" . female

}</lang>

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.

<lang awk>function F(n) { 

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

}

function M(n) { 

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

}

BEGIN { 

 for(i=0; i < 20; i++) {
   printf "%3d ", F(i)
 }
 print ""
 for(i=0; i < 20; i++) {
   printf "%3d ", M(i)
 }
 print ""

}</lang>

BASIC

Works with: QBasic

<lang qbasic>DECLARE FUNCTION f! (n!) DECLARE FUNCTION m! (n!)

FUNCTION f! (n!) 

   IF n = 0 THEN
       f = 1
   ELSE
       f = m(f(n - 1))
   END IF

END FUNCTION

FUNCTION m! (n!) 

   IF n = 0 THEN
       m = 0
   ELSE
       m = f(m(n - 1))
   END IF

END FUNCTION</lang>

BBC BASIC

<lang bbcbasic> @% = 3 : REM Column width 

     PRINT "F sequence:"
     FOR i% = 0 TO 20
       PRINT FNf(i%) ;
     NEXT
     PRINT
     PRINT "M sequence:"
     FOR i% = 0 TO 20
       PRINT FNm(i%) ;
     NEXT
     PRINT
     END
     
     DEF FNf(n%) IF n% = 0 THEN = 1 ELSE = n% - FNm(FNf(n% - 1))
     
     DEF FNm(n%) IF n% = 0 THEN = 0 ELSE = n% - FNf(FNm(n% - 1))</lang>

Output: 

F sequence:
  1  1  2  2  3  3  4  5  5  6  6  7  8  8  9  9 10 11 11 12 13
M sequence:
  0  0  1  2  2  3  4  4  5  6  6  7  7  8  9  9 10 11 11 12 12

Bc

<lang bc>define f(n) { 

 if ( n == 0 ) return(1);
 return(n - m(f(n-1)));

}

define m(n) { 

 if ( n == 0 ) return(0);
 return(n - f(m(n-1)));

}</lang>

Works with: GNU bc
Works with: OpenBSD bc

POSIX bc doesn't have the print statement.

<lang bc>/* GNU bc */ for(i=0; i < 19; i++) { 

 print f(i); print " ";

} print "\n"; for(i=0; i < 19; i++) { 

 print m(i); print " ";

} print "\n";</lang>

Bracmat

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

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

-1:?n&whl'(!n+1:~>20:?n&put$(F$!n " "))&put$\n
1  1  2  2  3  3  4  5  5  6  6  7  8  8  9  9  10  11  11  12  13

-1:?n&whl'(!n+1:~>20:?n&put$(M$!n " "))&put$\n
0  0  1  2  2  3  4  4  5  6  6  7  7  8  9  9  10  11  11  12  12</lang>

Brat

<lang brat>female = null #yes, this is necessary

male = { n | 

 true? n == 0
   { 0 }
   { n - female male(n - 1) }

}

female = { n | 

 true? n == 0
   { 1 }
   { n - male female(n - 1 ) }

}

p 0.to(20).map! { n | female n } p 0.to(20).map! { n | male n }</lang>

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)

<lang c>#include <stdio.h>

  1. include <stdlib.h>

/* let us declare our functions; indeed here we need 

  really only M declaration, so that F can "see" it
  and the compiler won't complain with a warning */

int F(const int n); int M(const int n);

int F(const int n) { 

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

}

int M(const int n) { 

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

}

int main(void) { 

 int i;
 for (i = 0; i < 20; i++)
   printf("%2d ", F(i));
 printf("\n");
 for (i = 0; i < 20; i++)
   printf("%2d ", M(i));
 printf("\n");
 return EXIT_SUCCESS;

}</lang>

C++

C++ has prior declaration rules similar to those stated above for 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. <lang cpp>#include <iostream>

  1. include <vector>
  2. include <iterator>

class Hofstadter { public: 

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

};

using namespace std;

int main() { 

 int i;
 vector<int> ra, rb;

 for(i=0; i < 20; i++) {
   ra.push_back(Hofstadter::F(i));
   rb.push_back(Hofstadter::M(i));
 }
 copy(ra.begin(), ra.end(),
      ostream_iterator<int>(cout, " "));
 cout << endl;
 copy(rb.begin(), rb.end(),
      ostream_iterator<int>(cout, " "));
 cout << endl;
 return 0;

}</lang>

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.

<lang cpp>class Hofstadter { public: 

 static int F(int n);
 static int M(int n);

};

int Hofstadter::F(int n) { 

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

}

int Hofstadter::M(int n) { 

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

}</lang>

C#

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

}</lang>

Clojure

<lang lisp>(declare F) ; forward reference

(defn M [n] 

 (if (zero? n)
   0
   (- n (F (M (dec n))))))

(defn F [n] 

 (if (zero? n)
   1
   (- n (M (F (dec n))))))</lang>

CoffeeScript

<lang coffeescript> F = (n) -> 

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

M = (n) -> 

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

console.log [0...20].map F console.log [0...20].map M </lang>

output

<lang> > 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 ] </lang>

Common Lisp

<lang lisp>(defun m (n) 

   (if (zerop n)
       0
       (- n (f (m (- n 1))))))

(defun f (n) 

   (if (zerop n)
       1
       (- n (m (f (- n 1))))))</lang>

D

<lang d>import std.stdio, std.algorithm, std.range;

int male(in int n) pure nothrow { 

   return n ? n - male(n - 1).female : 0;

}

int female(in int n) pure nothrow { 

   return n ? n - female(n - 1).male : 1;

}

void main() { 

   20.iota.map!female.writeln;
   20.iota.map!male.writeln;

}</lang>

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

Déjà Vu

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

Output:
0 1 
0 1 
1 2 
2 2 
2 3 
3 3 
4 4 
4 5 
5 5 
6 6 
6 6

Dart

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

main() { 

 String f="",m="";
 for(int i=0;i<20;i++) {
   m+="${M(i)} ";
   f+="${F(i)} ";
 }
 print("M: $m");
 print("F: $f");

}</lang>

Delphi

<lang Delphi> unit Hofstadter;

interface

type 

 THofstadterFemaleMaleSequences = class
 public
   class function F(n: Integer): Integer;
   class function M(n: Integer): Integer;
 end;

implementation

class function THofstadterFemaleMaleSequences.F(n: Integer): Integer; begin 

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

end;

class function THofstadterFemaleMaleSequences.M(n: Integer): Integer; begin 

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

end;

end. </lang>

E

In E, nouns (variable names) always refer to preceding definitions, so to have mutual recursion, either one must be forward-declared or we must use a recursive def construct. Either one of these is syntactic sugar for first binding the noun to an E promise (a reference with an undetermined target), then resolving the promise to the value.

Recursive def:

<lang e>def [F, M] := [ 

 fn n { if (n <=> 0) { 1 } else { n - M(F(n - 1)) } },
 fn n { if (n <=> 0) { 0 } else { n - F(M(n - 1)) } },

]</lang>

Forward declaration:

<lang e>def M 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)) } }</lang>

def M binds M to a promise, and stashes the resolver for that promise where bind can get to it. When def F... is executed, the function F closes over the promise which is the value of M. bind M... uses the resolver to resolve M to the provided definition. The recursive def operates similarly, except that it constructs promises for every variable on the left side ([F, M]), executes the right side ([fn ..., fn ...]) and collects the values, then resolves each promise to its corresponding value.

But you don't have to worry about that to use it.

Erlang

<lang erlang>-module(mutrec). -export([mutrec/0, f/1, m/1]).

f(0) -> 1; f(N) -> N - m(f(N-1)).

m(0) -> 0; m(N) -> N - f(m(N-1)).

mutrec() -> lists:map(fun(X) -> io:format("~w ", [f(X)]) end, lists:seq(0,19)), io:format("~n", []), lists:map(fun(X) -> io:format("~w ", [m(X)]) end, lists:seq(0,19)), io:format("~n", []).</lang>

Euphoria

<lang Euphoria>integer idM, idF

function F(integer n) 

   if n = 0 then
       return 1
   else
       return n - call_func(idM,{F(n-1)})
   end if

end function

idF = routine_id("F")

function M(integer n) 

   if n = 0 then
       return 0
   else
       return n - call_func(idF,{M(n-1)})
   end if

end function

idM = routine_id("M")</lang>

F#

<lang fsharp>let rec f n = 

   match n with
   | 0 -> 1
   | _ -> n - (m (f (n-1)))

and m n = 

   match n with
   | 0 -> 0
   | _ -> n - (f (m (n-1)))</lang>

Like OCaml, the let rec f .. and m ... construct indicates that the functions call themselves (rec) and each other (and).

Factor

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

M ( n -- n' ) dup 0 = [ dup 1 - M F - ] unless ;
F ( n -- n' ) dup 0 = [ drop 1 ] [ dup 1 - F M - ] if ;</lang>

FALSE

<lang false>[$[$1-f;!m;!-1-]?1+]f: [$[$1-m;!f;!- ]? ]m: [0[$20\>][\$@$@!." "1+]#%%]t: 

f; t;!"

"m; t;!</lang>

Fantom

<lang fantom> class Main { 

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

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

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

} </lang>

Forth

Forward references required for mutual recursion may be set up using DEFER. <lang forth>defer m

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

is m

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

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

Fortran

As long as the code of the two functions is inside the same "block" (module or program) we don't need special care. Otherwise, we should "load" at least the interface of the other function (each module will load mutually the other; of course the compiler won't enter in a infinite loop), e.g. by using a "use" (we do that if M and F function are inside different modules)

Works with: Fortran version 95 and later

<lang fortran>module MutualRec 

 implicit none

contains 

 pure recursive function m(n) result(r)
   integer :: r
   integer, intent(in) :: n
   if ( n == 0 ) then
      r = 0
      return
   end if
   r = n - f(m(n-1))
 end function m
 
 pure recursive function f(n) result(r)
   integer :: r
   integer, intent(in) :: n
   if ( n == 0 ) then
      r = 1
      return
   end if
   r = n - m(f(n-1))
 end function f

end module</lang>

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

<lang fortran>program testmutrec 

 use MutualRec
 implicit none

 integer :: i
 integer, dimension(20) :: a = (/ (i, i=0,19) /), b = (/ (i, i=0,19) /)
 integer, dimension(20) :: ra, rb
 
 forall(i=1:20) 
    ra(i) = m(a(i))
    rb(i) = f(b(i))
 end forall

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

end program testmutrec</lang>

Go

It just works. No special pre-declaration is necessary. <lang go>package main import "fmt"

func F(n int) int { 

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

}

func M(n int) int { 

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

}

func main() { 

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

}</lang>

Groovy

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

Test program: <lang groovy>println 'f(0..20): ' + (0..20).collect { f(it) } println 'm(0..20): ' + (0..20).collect { m(it) }</lang>

Output: 

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

Haskell

Haskell's definitions constructs (at the top level, or inside a let or where construct) are always mutually-recursive: <lang haskell>f 0 = 1 f n | n > 0 = n - m (f $ n-1)

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

main = do 

      print $ map f [0..19]
      print $ map m [0..19]</lang>

Icon and Unicon

<lang Icon>procedure main(arglist) every write(F(!arglist)) # F of all arguments end

procedure F(n) if integer(n) >= 0 then 

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

end

procedure M(n) if integer(n) >= 0 then 

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

end</lang>

J

<lang j>F =: 1:`(- M @ $: @ <:) @.* M."0 M =: 0:`(- F @ $: @ <:) @.* M."0</lang>

Example use:

<lang j> F i. 20 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12</lang>

Java

Translation of: C

<lang java5>public static int f(final int n) { 

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

}

public static int m(final int n) { 

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

}

public static void main(final String args[]) { 

for (int i = 0; i < 20; i++)
 System.out.println(f(i));
System.out.println();
for (i = 0; i < 20; i++)
 System.out.println(m(i));

}</lang>

JavaScript

<lang javascript>function F(n) { 

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

}

function M(n) { 

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

}

var 

out = {F: [], M: []},
i;

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

out.F.push(F(i));
out.M.push(M(i));

} print(out.F + "\n" + out.M);</lang> outputs: 

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

Julia

<lang julia>F(n) = n < 1 ? one(n) : n - M(F(n - 1)) M(n) = n < 1 ? zero(n) : n - F(M(n - 1))</lang> Output: 

julia> [F(i) for i = 0:19], [M(i) for i = 0:19]
([1,1,2,2,3,3,4,5,5,6,6,7,8,8,9,9,10,11,11,12],[0,0,1,2,2,3,4,4,5,6,6,7,7,8,9,9,10,11,11,12])

Liberty BASIC

<lang lb> print "F sequence." for i = 0 to 20 print f(i);" "; next print print "M sequence." for i = 0 to 20 print m(i);" "; next

end

function f(n) 

   if n = 0 then
       f = 1
   else
       f = n - m(f(n - 1))
   end if
   end function

function m(n) 

   if n = 0 then
       m = 0
   else
       m = n - f(m(n - 1))
   end if
   end function

</lang>

Output:
F sequence.
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13
M sequence.
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12

Like Lisp, symbols in Logo are late-bound so no special syntax is required for forward references.

<lang logo>to m :n 

 if 0 = :n [output 0]
 output :n - f m :n-1

end to f :n 

 if 0 = :n [output 1]
 output :n - m f :n-1

end

show cascade 20 [lput m #-1 ?] [] [1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12] show cascade 20 [lput f #-1 ?] [] [0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12]</lang>

LSL

To test it yourself; rez a box on the ground, and add the following as a New Script. <lang LSL>integer iDEPTH = 100; integer f(integer n) { if(n==0) { return 1; } else { return n-m(f(n - 1)); } } integer m(integer n) { if(n==0) { return 0; } else { return n-f(m(n - 1)); } } default { state_entry() { integer x = 0; string s = ""; for(x=0 ; x<iDEPTH ; x++) { s += (string)(f(x))+" "; } llOwnerSay(llList2CSV(llParseString2List(s, [" "], []))); s = ""; for(x=0 ; x<iDEPTH ; x++) { s += (string)(m(x))+" "; } llOwnerSay(llList2CSV(llParseString2List(s, [" "], []))); } }</lang> Output: 

1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 8, 8, 9, 9, 10, 11, 11, 12, 13, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 21, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 34, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47, 48, 48, 49, 50, 50, 51, 51, 52, 53, 53, 54, 55, 55, 56, 56, 57, 58, 58, 59, 59, 60, 61, 61
0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6, 7, 7, 8, 9, 9, 10, 11, 11, 12, 12, 13, 14, 14, 15, 16, 16, 17, 17, 18, 19, 19, 20, 20, 21, 22, 22, 23, 24, 24, 25, 25, 26, 27, 27, 28, 29, 29, 30, 30, 31, 32, 32, 33, 33, 34, 35, 35, 36, 37, 37, 38, 38, 39, 40, 40, 41, 42, 42, 43, 43, 44, 45, 45, 46, 46, 47, 48, 48, 49, 50, 50, 51, 51, 52, 53, 53, 54, 54, 55, 56, 56, 57, 58, 58, 59, 59, 60, 61, 61

Lua

<lang 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</lang>

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:

<lang lua> 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</lang>

M4

<lang m4>define(`female',`ifelse(0,$1,1,`eval($1 - male(female(decr($1))))')')dnl define(`male',`ifelse(0,$1,0,`eval($1 - female(male(decr($1))))')')dnl define(`loop',`ifelse($1,$2,,`$3($1) loop(incr($1),$2,`$3')')')dnl loop(0,20,`female') loop(0,20,`male')</lang>

Mathematica

Without caching: <lang Mathematica>f[0]:=1 m[0]:=0 f[n_]:=n-m[f[n-1]] m[n_]:=n-f[m[n-1]]</lang> With caching: <lang Mathematica>f[0]:=1 m[0]:=0 f[n_]:=f[n]=n-m[f[n-1]] m[n_]:=m[n]=n-f[m[n-1]]</lang> Example finding f(1) to f(30) and m(1) to m(30): <lang Mathematica>m /@ Range[30] f /@ Range[30]</lang> gives back: <lang Mathematica>{0,1,2,2,3,4,4,5,6,6,7,7,8,9,9,10,11,11,12,12,13,14,14,15,16,16,17,17,18,19} {1,2,2,3,3,4,5,5,6,6,7,8,8,9,9,10,11,11,12,13,13,14,14,15,16,16,17,17,18,19}</lang>

MATLAB

female.m: <lang MATLAB>function Fn = female(n) 

   if n == 0
       Fn = 1;
       return
   end
   
   Fn = n - male(female(n-1));

end</lang>

male.m: <lang MATLAB>function Mn = male(n) 

   if n == 0
       Mn = 0;
       return
   end
   
   Mn = n - female(male(n-1));

end</lang>

Sample Output: <lang MATLAB>>> n = (0:10); >> arrayfun(@female,n)

ans = 

    1     1     2     2     3     3     4     5     5     6     6

>> arrayfun(@male,n)

ans = 

    0     0     1     2     2     3     4     4     5     6     6</lang>

Maxima

<lang maxima>f[0]: 1$ m[0]: 0$ f[n] := n - m[f[n - 1]]$ m[n] := n - f[m[n - 1]]$

makelist(f[i], i, 0, 10); [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6]

makelist(m[i], i, 0, 10); [0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6]

remarray(m, f)$

f(n) := if n = 0 then 1 else n - m(f(n - 1))$ m(n) := if n = 0 then 0 else n - f(m(n - 1))$

makelist(f(i), i, 0, 10); [1, 1, 2, 2, 3, 3, 4, 5, 5, 6, 6]

makelist(m(i), i, 0, 10); [0, 0, 1, 2, 2, 3, 4, 4, 5, 6, 6]

remfunction(f, m)$</lang>

Mercury

<lang>

- module mutual_recursion.
- interface.
- import_module io.
- pred main(io::di, io::uo) is det.
- implementation.
- import_module int, list.

main(!IO) :- 

  io.write(list.map(f, 0..19), !IO), io.nl(!IO),
  io.write(list.map(m, 0..19), !IO), io.nl(!IO).
- func f(int) = int.

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

- func m(int) = int.

m(N) = ( if N = 0 then 0 else N - f(m(N - 1)) ). </lang>

MMIX

<lang mmix> LOC Data_Segment

GREG @ NL BYTE #a,0 GREG @ buf OCTA 0,0

t IS $128 Ja IS $127

LOC #1000

GREG @ // print 2 digits integer with trailing space to StdOut // reg $3 contains int to be printed bp IS $71 0H GREG #0000000000203020 prtInt STO 0B,buf % initialize buffer LDA bp,buf+7 % points after LSD % REPEAT 1H SUB bp,bp,1 % move buffer pointer DIV $3,$3,10 % divmod (x,10) GET t,rR % get remainder INCL t,'0' % make char digit STB t,bp % store digit PBNZ $3,1B % UNTIL no more digits LDA $255,bp TRAP 0,Fputs,StdOut % print integer GO Ja,Ja,0 % 'return'

// Female function F GET $1,rJ % save return addr PBNZ $0,1F % if N != 0 then F N INCL $0,1 % F 0 = 1 PUT rJ,$1 % restore return addr POP 1,0 % return 1 1H SUBU $3,$0,1 % N1 = N - 1 PUSHJ $2,F % do F (N - 1) ADDU $3,$2,0 % place result in arg. reg. PUSHJ $2,M % do M F ( N - 1) PUT rJ,$1 % restore ret addr SUBU $0,$0,$2 POP 1,0 % return N - M F ( N - 1 )

// Male function M GET $1,rJ PBNZ $0,1F PUT rJ,$1 POP 1,0 % return M 0 = 0 1H SUBU $3,$0,1 PUSHJ $2,M ADDU $3,$2,0 PUSHJ $2,F PUT rJ,$1 SUBU $0,$0,$2 POP 1,0 $ return N - F M ( N - 1 )

// do a female run Main SET $1,0 % for (i=0; i<25; i++){ 1H ADDU $4,$1,0 % PUSHJ $3,F % F (i) GO Ja,prtInt % print F (i) INCL $1,1 CMP t,$1,25 PBNZ t,1B % } LDA $255,NL TRAP 0,Fputs,StdOut // do a male run SET $1,0 % for (i=0; i<25; i++){ 1H ADDU $4,$1,0 % PUSHJ $3,M % M (i) GO Ja,prtInt % print M (i) INCL $1,1 CMP t,$1,25 PBNZ t,1B % } LDA $255,NL TRAP 0,Fputs,StdOut TRAP 0,Halt,0</lang>

Output: 

~/MIX/MMIX/Rosetta> mmix mutualrecurs1
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 13 14 14 15
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12 13 14 14 15

Nemerle

<lang Nemerle>using System; using System.Console;

module Hofstadter { 

   F(n : int) : int
   {
       |0 => 1
       |_ => n - M(F(n - 1))
   }
   
   M(n : int) : int
   {
       |0 => 0
       |_ => n - F(M(n - 1))
   }
   
   Main() : void
   {
       foreach (n in [0 .. 20]) Write("{0} ", F(n));
       WriteLine();
       foreach (n in [0 .. 20]) Write("{0} ", M(n));
   }

}</lang>

Objective-C

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

<lang objc>#import <Foundation/Foundation.h>

@interface Hofstadter : NSObject + (int)M: (int)n; + (int)F: (int)n; @end

@implementation Hofstadter + (int)M: (int)n { 

 if ( n == 0 ) return 0;
 return n - [self F: [self M: (n-1)]];

} + (int)F: (int)n { 

 if ( n == 0 ) return 1;
 return n - [self M: [self F: (n-1)]];

} @end

int main() { 

 int i;

 for(i=0; i < 20; i++) {
   printf("%3d ", [Hofstadter F: i]);
 }
 printf("\n");
 for(i=0; i < 20; i++) {
   printf("%3d ", [Hofstadter M: i]);
 }
 printf("\n");
 return 0;

}</lang>

Objeck

Translation of: C

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

} </lang>

OCaml

<lang ocaml>let rec f = function 

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

and m = function 

 | 0 -> 0
 | n -> n - f(m(n-1))
</lang>

The let rec f ... and m ... construct indicates that the functions call themselves (rec) and each other (and).

Octave

We don't need to pre-declare or specify in some other way a function that will be defined later; but both must be declared before their use.
(The code is written to handle vectors, as the testing part shows)

<lang octave>function r = F(n) 

 for i = 1:length(n)
   if (n(i) == 0)
     r(i) = 1;
   else
     r(i) = n(i) - M(F(n(i)-1));
   endif
 endfor

endfunction

function r = M(n) 

 for i = 1:length(n)
   if (n(i) == 0)
     r(i) = 0;
   else
     r(i) = n(i) - F(M(n(i)-1));
   endif
 endfor

endfunction</lang>

<lang octave># testing ra = F([0:19]); rb = M([0:19]); disp(ra); disp(rb);</lang>

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.

<lang c>#include <order/interpreter.h>

  1. define ORDER_PP_DEF_8f \

ORDER_PP_FN(8fn(8N, \ 

               8if(8is_0(8N),                  \
                   1,                          \
                   8sub(8N, 8m(8f(8dec(8N)))))))
  1. define ORDER_PP_DEF_8m \

ORDER_PP_FN(8fn(8N, \ 

               8if(8is_0(8N),                  \
                   0,                          \
                   8sub(8N, 8f(8m(8dec(8N)))))))

//Test ORDER_PP(8for_each_in_range(8fn(8N, 8print(8f(8N))), 0, 19)) ORDER_PP(8for_each_in_range(8fn(8N, 8print(8m(8N))), 0, 19))</lang>

Oz

<lang oz>declare 

 fun {F N}
    if N == 0 then 1
    elseif N > 0 then N - {M {F N-1}}
    end
 end

 fun {M N}
    if N == 0 then 0
    elseif N > 0 then N - {F {M N-1}}
    end
 end

in 

 {Show {Map {List.number 0 9 1} F}}
 {Show {Map {List.number 0 9 1} M}}</lang>

PARI/GP

<lang parigp>F(n)=if(n,n-M(F(n-1)),1) M(n)=if(n,n-F(M(n-1)),0)</lang>

Pascal

In Pascal we need to pre-declare functions/procedures; to do so, the forward statement is used.

<lang pascal>Program MutualRecursion;

{M definition comes after F which uses it} function M(n : Integer) : Integer; forward;

function F(n : Integer) : Integer; begin 

  if n = 0 then
     F := 1
  else
     F := n - M(F(n-1));

end;

function M(n : Integer) : Integer; begin 

  if n = 0 then
     M := 0
  else
     M := n - F(M(n-1));

end;

var 

  i : Integer;

begin 

  for i := 0 to 19 do begin
     write(F(i) : 4)
  end;
  writeln;
  for i := 0 to 19 do begin
     write(M(i) : 4)
  end;
  writeln;

end.</lang>

Perl

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

  1. Usage:

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

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

}</lang>

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

Perl 6

A direct translation of the definitions of and : <lang perl6>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;</lang>

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

PHP

<lang php><?php function F($n) { 

 if ( $n == 0 ) return 1;
 return $n - M(F($n-1));

}

function M($n) { 

 if ( $n == 0) return 0;
 return $n - F(M($n-1));

}

$ra = array(); $rb = array(); for($i=0; $i < 20; $i++) { 

 array_push($ra, F($i));
 array_push($rb, M($i));

} echo implode(" ", $ra) . "\n"; echo implode(" ", $rb) . "\n"; ?></lang>

PicoLisp

<lang PicoLisp>(de f (N) 

  (if (=0 N)
     1
     (- N (m (f (dec N)))) ) )

(de m (N) 

  (if (=0 N)
     0
     (- N (f (m (dec N)))) ) )</lang>

PL/I

<lang PL/I> test: procedure options (main);

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

  declare n fixed;
  if n <= 0 then return (0);
  else return ( n - F(M(n-1)) );

end M;

F: procedure (n) returns (fixed) recursive; 

  declare n fixed;
  if n <= 0 then return (1);
  else return ( n - M(F(n-1)) );

end F; 

  declare i fixed;

  do i = 1 to 15;
     put skip list ( F(i), M(i) );
  end;

end test; </lang>

PostScript

<lang> /female{ /n exch def n 0 eq {1} { n n 1 sub female male sub }ifelse }def

/male{ /n exch def n 0 eq {0} { n n 1 sub male female sub }ifelse }def </lang>

Library: initlib

<lang postscript> /F { { 

   {0 eq} {pop 1} is?
   {0 gt} {dup 1 sub F M sub} is?

} cond }.

/M { { 

   {0 eq} {pop 0} is?
   {0 gt} {dup 1 sub M F sub} is?

} cond }.

</lang>

PowerShell

<lang powershell>function F($n) { 

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

}

function M($n) { 

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

}</lang>

Prolog

<lang prolog>female(0,1). female(N,F) :- N>0, N1 is N-1, female(N1,R), male(R, R1), F is N-R1.

male(0,0). male(N,F) :- N>0, N1 is N-1, male(N1,R), female(R, R1), F is N-R1.</lang>

Works with: GNU Prolog

<lang prolog>flist(S) :- for(X, 0, S), female(X, R), format('~d ', [R]), fail. mlist(S) :- for(X, 0, S), male(X, R), format('~d ', [R]), fail.</lang>

Testing 

| ?- flist(19).
1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 

no
| ?- mlist(19).
0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12

Pure

The Pure definitions very closely maps to the mathematical definitions.

<lang pure>F 0 = 1; M 0 = 0; F n = n - M(F(n-1)) if n>0; M n = n - F(M(n-1)) if n>0;</lang>

<lang pure>> let females = map F (0..10); females; [1,1,2,2,3,3,4,5,5,6,6] > let males = map M (0..10); males; [0,0,1,2,2,3,4,4,5,6,6]</lang>

PureBasic

<lang PureBasic>Declare M(n)

Procedure F(n) 

 If n = 0
   ProcedureReturn 1
 ElseIf n > 0
   ProcedureReturn n - M(F(n - 1))
 EndIf

EndProcedure

Procedure M(n) 

 If n = 0
   ProcedureReturn 0
 ElseIf n > 0
   ProcedureReturn n - F(M(n - 1))
 EndIf

EndProcedure

Define i If OpenConsole() 

 For i = 0 To 19
   Print(Str(F(i)))
   If i = 19
     Continue
   EndIf
   Print(", ")
 Next
 
 PrintN("")
 For i = 0 To 19
   Print(Str(M(i)))
   If i = 19
     Continue
   EndIf
   Print(", ")
 Next 
     
 Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
 Input()
 CloseConsole()

EndIf</lang> Sample output: 

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

Python

Works with: Python version 3.0

.

Works with: Python version 2.6


<lang python>def F(n): return 1 if n == 0 else n - M(F(n-1)) def M(n): return 0 if n == 0 else n - F(M(n-1))

print ([ F(n) for n in range(20) ]) print ([ M(n) for n in range(20) ])</lang>

Output: 

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

In python there is no need to pre-declare M for it to be used in the definition of F. (However M must be defined before F calls it).

R

<lang R>F <- function(n) ifelse(n == 0, 1, n - M(F(n-1))) M <- function(n) ifelse(n == 0, 0, n - F(M(n-1)))</lang>

<lang R>print.table(lapply(0:19, M)) print.table(lapply(0:19, F))</lang>

REBOL

<lang REBOL>REBOL [ 

   Title: "Mutual Recursion"
   Date: 2009-12-14
   Author: oofoe
   URL: http://rosettacode.org/wiki/Mutual_Recursion

References: [1] ]

f: func [ "Female." n [integer!] "Value." ] [either 0 = n [1][n - m f n - 1]]

m: func [ "Male." n [integer!] "Value." ] [either 0 = n [0][n - f m n - 1]]

fs: [] ms: [] for i 0 19 1 [append fs f i append ms m i] print ["F:" mold fs crlf "M:" mold ms]</lang>

Output: 

F: [1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12] 
M: [0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12]

Racket

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

REXX

vanilla

This version uses vertical formatting. <lang rexx>/*REXX program shows mutual recursion (via Hofstadter Male & Female seq)*/ arg lim .; if lim== then lim=40; pad=left(,20) 

      do j=0 to lim;     jj=Jw(j);     ff=F(j);     mm=M(j)
      say    pad    'F('jj") ="    Jw(ff)    pad    'M('jj") ="    Jw(mm)   
      end   /*j*/

exit /*stick a fork in it, we're done.*/ /*─────────────────────────────────────F, M, Jw subroutines────────────*/ F: procedure; arg n; if n==0 then return 1; return n-M(F(n-1)) M: procedure; arg n; if n==0 then return 0; return n-F(M(n-1)) Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/</lang> output (using the default of 40): 

                     F( 0) =  1                      M( 0) =  0
                     F( 1) =  1                      M( 1) =  0
                     F( 2) =  2                      M( 2) =  1
                     F( 3) =  2                      M( 3) =  2
                     F( 4) =  3                      M( 4) =  2
                     F( 5) =  3                      M( 5) =  3
                     F( 6) =  4                      M( 6) =  4
                     F( 7) =  5                      M( 7) =  4
                     F( 8) =  5                      M( 8) =  5
                     F( 9) =  6                      M( 9) =  6
                     F(10) =  6                      M(10) =  6
                     F(11) =  7                      M(11) =  7
                     F(12) =  8                      M(12) =  7
                     F(13) =  8                      M(13) =  8
                     F(14) =  9                      M(14) =  9
                     F(15) =  9                      M(15) =  9
                     F(16) = 10                      M(16) = 10
                     F(17) = 11                      M(17) = 11
                     F(18) = 11                      M(18) = 11
                     F(19) = 12                      M(19) = 12
                     F(20) = 13                      M(20) = 12
                     F(21) = 13                      M(21) = 13
                     F(22) = 14                      M(22) = 14
                     F(23) = 14                      M(23) = 14
                     F(24) = 15                      M(24) = 15
                     F(25) = 16                      M(25) = 16
                     F(26) = 16                      M(26) = 16
                     F(27) = 17                      M(27) = 17
                     F(28) = 17                      M(28) = 17
                     F(29) = 18                      M(29) = 18
                     F(30) = 19                      M(30) = 19
                     F(31) = 19                      M(31) = 19
                     F(32) = 20                      M(32) = 20
                     F(33) = 21                      M(33) = 20
                     F(34) = 21                      M(34) = 21
                     F(35) = 22                      M(35) = 22
                     F(36) = 22                      M(36) = 22
                     F(37) = 23                      M(37) = 23
                     F(38) = 24                      M(38) = 24
                     F(39) = 24                      M(39) = 24
                     F(40) = 25                      M(40) = 25

with memoization

This version uses memoization as well as a horizontal output format.

The optimization due to memoization is faster by many orders of magnitude. <lang rexx>/*REXX program shows mutual recursion (via Hofstadter Male & Female seq)*/ arg lim .;if lim== then lim=99; hm.=; hm.0=0; hf.=; hf.0=1; Js=; Fs=; Ms= 

               do j=0 to lim;                   ff=F(j);         mm=M(j)
                        Js=Js jW(j);   Fs=Fs jw(ff);    Ms=Ms jW(mm)
               end   /*j*/

say 'Js=' Js say 'Fs=' Fs say 'Ms=' Ms exit /*stick a fork in it, we're done.*/ /*─────────────────────────────────────F, M, Jw subroutines────────────*/ F: procedure expose hm. hf.; arg n; if hf.n== then hf.n=n-M(F(n-1)); return hf.n M: procedure expose hm. hf.; arg n; if hm.n== then hm.n=n-F(M(n-1)); return hm.n Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/</lang> output (using the default of 99): 

Js=  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
Fs=  1  1  2  2  3  3  4  5  5  6  6  7  8  8  9  9 10 11 11 12 13 13 14 14 15 16 16 17 17 18 19 19 20 21 21 22 22 23 24 24 25 25 26 27 27 28 29 29 30 30 31 32 32 33 34 34 35 35 36 37 37 38 38 39 40 40 41 42 42 43 43 44 45 45 46 46 47 48 48 49 50 50 51 51 52 53 53 54 55 55 56 56 57 58 58 59 59 60 61 61
Ms=  0  0  1  2  2  3  4  4  5  6  6  7  7  8  9  9 10 11 11 12 12 13 14 14 15 16 16 17 17 18 19 19 20 20 21 22 22 23 24 24 25 25 26 27 27 28 29 29 30 30 31 32 32 33 33 34 35 35 36 37 37 38 38 39 40 40 41 42 42 43 43 44 45 45 46 46 47 48 48 49 50 50 51 51 52 53 53 54 54 55 56 56 57 58 58 59 59 60 61 61

with memoization, specific entry

This version is identical in function to the previous example, but it also can compute and
display a specific request (indicated by a negative number for the argument). <lang rexx>/*REXX program shows mutual recursion (via Hofstadter Male & Female seq)*/ /*If LIM is negative, only show a single result for the abs(lim) entry.*/

parse arg lim .; if lim== then lim=99; aLim=abs(lim) parse var lim . hm. hf. Js Fs Ms; hm.0=0; hf.0=1 

               do j=0 to Alim;               ff=F(j);           mm=M(j)
                     Js=Js jW(j);     Fs=Fs jw(ff);      Ms=Ms jW(mm)
               end

if lim>0 then say 'Js=' Js; else say 'J('aLim")=" word(Js,aLim+1) if lim>0 then say 'Fs=' Fs; else say 'F('aLim")=" word(Fs,aLim+1) if lim>0 then say 'Ms=' Ms; else say 'M('aLim")=" word(Ms,aLim+1) exit /*stick a fork in it, we're done.*/ /*─────────────────────────────────────F, M, Jw subroutines────────────*/ F: procedure expose hm. hf.; arg n; if hf.n== then hf.n=n-M(F(n-1)); return hf.n M: procedure expose hm. hf.; arg n; if hm.n== then hm.n=n-F(M(n-1)); return hm.n Jw: return right(arg(1),length(lim)) /*right justifies # for nice look*/</lang> output using the input of: -70000 

J(70000)= 70000
F(70000)= 43262
M(70000)= 43262

output using the input of a ¼ million: -250000 

J(250000)= 250000
F(250000)= 154509
M(250000)= 154509

Ruby

<lang ruby>def F(n) 

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

end def M(n) 

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

end

p (Array.new(20) {|n| F(n) }) p (Array.new(20) {|n| M(n) })</lang>

Output: 

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

In ruby there is no need to pre-declare M for it to be used in the definition of F. (However M must be defined before F calls it).

Run BASIC

<lang Runbasic>print "F sequence:"; for i = 0 to 20 

 print f(i);" ";

next i print :print "M sequence:"; for i = 0 to 20 

 print m(i);" ";

next i end

function f(n) 

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

end function

function m(n) 

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

end function</lang> Output: 

F sequence:1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 
M sequence:0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12

Rust

<lang rust>fn f(n: int) -> int { 

   match n {
       0 => 1,
       _ => n - m(f(n - 1))
   }

}

fn m(n: int) -> int { 

   match n {
       0 => 0,
       _ => n - f(m(n - 1))
   }

}

fn main() { 

   for i in range(0, 20).map(f) {
       print!("{} ", i);
   }
   println!("")

   for i in range(0, 20).map(m) {
       print!("{} ", i);
   }
   println!("")

}</lang> Output: 

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

Sather

<lang sather>class MAIN is 

 f(n:INT):INT
   pre n >= 0
 is
   if n = 0 then return 1; end;
   return n - m(f(n-1));
 end;

 m(n:INT):INT
   pre n >= 0
 is
   if n = 0 then return 0; end;
   return n - f(m(n-1));
 end;

 main is
   loop i ::= 0.upto!(19);
     #OUT + #FMT("%2d ", f(i));
   end;
   #OUT + "\n";
   loop i ::= 0.upto!(19);
     #OUT + #FMT("%2d ", m(i));
   end;
 end;

end;</lang>

There's no need to pre-declare someway F or M.

Scala

<lang scala>def F(n:Int):Int = 

 if (n == 0) 1 else n - M(F(n-1))

def M(n:Int):Int = 

 if (n == 0) 0 else n - F(M(n-1))

println((0 until 20).map(F).mkString(", ")) println((0 until 20).map(M).mkString(", "))</lang>

Output: 

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

Scheme

define declarations are automatically mutually recursive: <lang scheme>(define (F n) 

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

(define (M n) 

 (if (= n 0) 0
     (- n (F (M (- n 1))))))</lang>

If you wanted to use a let-like construct to create local bindings, you would do the following. The define construct above is just a syntactic sugar for the following where the entire rest of the scope is used as the body. <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))))))))
 (F 19)) # evaluates to 12</lang>

The letrec indicates that the definitions can be recursive, and fact that we placed these two in the same letrec block makes them mutually recursive.

Seed7

<lang seed7>$ include "seed7_05.s7i";

const func integer: m (in integer: n) is forward;

const func integer: f (in integer: n) is func 

 result
   var integer: res is 0;
 begin
   if n = 0 then
     res := 1;
   else
     res := n - m(f(n - 1));
   end if;
 end func;

const func integer: m (in integer: n) is func 

 result
   var integer: res is 0;
 begin
   if n = 0 then
     res := 0;
   else
     res := n - f(m(n - 1));
   end if;
 end func;

const proc: main is func 

 local
   var integer: i is 0;
 begin
   for i range 0 to 19 do
     write(f(i) lpad 3);
   end for;
   writeln;
   for i range 0 to 19 do
     write(m(i) lpad 3);
   end for;
   writeln;
 end func;</lang>

Output: 

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

Smalltalk

Using block closure.

<lang smalltalk>|F M ra rb|

F := [ :n | 

 (n == 0)
   ifTrue: [ 1 ]
   ifFalse: [ n - (M value: (F value: (n-1))) ]

].

M := [ :n | 

 (n == 0)
   ifTrue: [ 0 ]
   ifFalse: [ n - (F value: (M value: (n-1))) ]

].

ra := OrderedCollection new. rb := OrderedCollection new. 0 to: 19 do: [ :i | 

 ra add: (F value: i).
 rb add: (M value: i)

].

ra displayNl. rb displayNl.</lang>

SNOBOL4

<lang SNOBOL4> define('f(n)') :(f_end) f f = eq(n,0) 1 :s(return) 

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

f_end 

       define('m(n)') :(m_end)

m m = eq(n,0) 0 :s(return) 

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

m_end

  • # Test and display

L1 s1 = s1 m(i) ' ' ; s2 = s2 f(i) ' ' 

       i = le(i,25) i + 1 :s(L1)
       output = 'M: ' s1; output = 'F: ' s2

end</lang>

Output: 

M: 0 0 1 2 2 3 4 4 5 6 6 7 7 8 9 9 10 11 11 12 12 13 14 14 15 16 16
F: 1 1 2 2 3 3 4 5 5 6 6 7 8 8 9 9 10 11 11 12 13 13 14 14 15 16 16

SNUSP

The program shown calculates F(3) and demonstrates simple and mutual recursion. <lang SNUSP> /======\ F==!/=!\?\+# | />-<-\ 

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

$+++/======|====/ 

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

M==!\=!\?\#| | | 

        \@/-@/@/===?\<#
       ^       \>-<-/
       | ^  ^ ^ ^
       | |  | | subtract from n
       | |  | mutual recursion
       | |  recursion
       | n-1
       check for zero</lang>

Standard ML

<lang sml>fun f 0 = 1 

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

and m 0 = 0 

 | m n = n - f (m (n-1))
</lang>

The fun construct creates recursive functions, and the and allows a group of functions to call each other. The above is just a shortcut for the following:

<lang sml>val rec f = fn 0 => 1 

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

and m = fn 0 => 0 

        | n => n - f (m (n-1))
</lang>

which indicates that the functions call themselves (rec) and each other (and).

Swift

It just works. No special pre-declaration is necessary. <lang swift>func F(n: Int) -> Int { 

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

}

func M(n: Int) -> Int { 

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

}

for i in 0..20 { 

 print("\(F(i)) ")

} println() for i in 0..20 { 

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

} println()</lang>

Tcl

<lang tcl>proc m {n} { 

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

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

   }

} proc f {n} { 

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

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

   }

}

for {set i 0} {$i < 20} {incr i} { 

   puts -nonewline [f $i];
   puts -nonewline " ";

} puts "" for {set i 0} {$i < 20} {incr i} { 

   puts -nonewline [m $i];
   puts -nonewline " ";

} puts ""</lang>

TI-89 BASIC

<lang ti89b>Define F(n) = when(n=0, 1, n - M(F(n - 1))) Define M(n) = when(n=0, 0, n - F(M(n - 1)))</lang>

TXR

<lang txr>@(do 

  (defun f (n)
    (if (>= 0 n)
      1
      (- n (m (f (- n 1))))))

  (defun m (n)
    (if (>= 0 n)
      0
      (- n (f (m (- n 1))))))

  (each ((n (range 0 15)))
    (format t "f(~s) = ~s; m(~s) = ~s\n" n (f n) n (m n))))</lang>

$ txr mutual-recursion.txr
f(0) = 1; m(0) = 0
f(1) = 1; m(1) = 0
f(2) = 2; m(2) = 1
f(3) = 2; m(3) = 2
f(4) = 3; m(4) = 2
f(5) = 3; m(5) = 3
f(6) = 4; m(6) = 4
f(7) = 5; m(7) = 4
f(8) = 5; m(8) = 5
f(9) = 6; m(9) = 6
f(10) = 6; m(10) = 6
f(11) = 7; m(11) = 7
f(12) = 8; m(12) = 7
f(13) = 8; m(13) = 8
f(14) = 9; m(14) = 9
f(15) = 9; m(15) = 9

UNIX Shell

Works with: Bourne Again SHell

<lang bash>M() { 

   local n
   n=$1
   if $n -eq 0 ; then

echo -n 0 

   else

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

   fi

}

F() { 

   local n
   n=$1
   if $n -eq 0 ; then

echo -n 1 

   else

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

   fi

}

for((i=0; i < 20; i++)); do 

   F $i
   echo -n " "

done echo for((i=0; i < 20; i++)); do 

   M $i
   echo -n " "

done echo</lang>

Ursala

Forward declarations are not an issue in Ursala, which allows any definition to depend on any symbol declared within the same scope. However, cyclic dependences are not accepted unless the programmer explicitly accounts for their semantics. If the recurrence can be solved using a fixed point combinator, the compiler can be directed to use one by the #fix directive as shown, in this case with one of a family of functional fixed point combinators from a library. (There are easier ways to define these functions in Ursala than by mutual recursion, but fixed points are useful for other things as well.)

<lang Ursala>#import std

  1. import nat
  2. import sol
  1. fix general_function_fixer 0

F = ~&?\1! difference^/~& M+ F+ predecessor M = ~&?\0! difference^/~& F+ M+ predecessor</lang> This test program applies both functions to the first twenty natural numbers. <lang Ursala>#cast %nLW

test = ^(F*,M*) iota 20</lang> output: 

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

x86 Assembly

Works with: nasm

Since all "labels" (symbols), if not local, can be seen by the whole code in the same source unit, we don't need special care to let the subroutine func_f call func_m. If the function would have been in another source unit, we should have declared it extern (the linker will resolve the symbol), as done for printf.
(It must be linked with the C standard library libc or similar and a startup code; lazyly a gcc mutrec.o works, being mutrec.o produced by e.g. nasm -f elf mutrec.asm) <lang asm> global main extern printf

section .text

func_f mov eax, [esp+4] cmp eax, 0 jz f_ret dec eax push eax call func_f mov [esp+0], eax call func_m add esp, 4 mov ebx, [esp+4] sub ebx, eax mov eax, ebx ret f_ret mov eax, 1 ret

func_m mov eax, [esp+4] cmp eax, 0 jz m_ret dec eax push eax call func_m mov [esp+0], eax call func_f add esp, 4 mov ebx, [esp+4] sub ebx, eax mov eax, ebx ret m_ret xor eax, eax ret

main mov edx, func_f call output_res mov edx, func_m call output_res ret

output_res xor ecx, ecx loop0 push ecx call edx 

       push    edx

push eax push form call printf add esp, 8

pop edx 

       pop     ecx

inc ecx cmp ecx, 20 jnz loop0

push newline call printf add esp, 4

ret


section .rodata form db '%d ',0 newline db 10,0

end</lang>

XPL0

<lang XPL0>code ChOut=8, CrLf=9, IntOut=11;

ffunc M; \forward-referenced function declaration

func F(N); int N; return if N=0 then 1 else N - M(F(N-1));

func M(N); int N; return if N=0 then 0 else N - F(M(N-1));

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

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

CrLf(0); ]</lang>

Output: 

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

zkl

zkl doesn't like referencing undefined objects so there is a bit of sleaze here. <lang zkl>fcn f(n,m){if(n==0)return(1); n-m(f(n-1,m),f)} fcn m(n,f){if(n==0)return(0); n-f(m(n-1,f),m)} [0..19].apply(f.fp1(m)) [0..19].apply(m.fp1(f))</lang>

Output:
L(1,1,2,2,3,3,4,5,5,6,6,7,8,8,9,9,10,11,11,12)
L(0,0,1,2,2,3,4,4,5,6,6,7,7,8,9,9,10,11,11,12)
Retrieved from "https://rosettacode.org/wiki/Mutual_recursion?oldid=106660"