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).
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>
ALGOL 68
<lang algol>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
AWK
In AWK it is enough that both functions are defined before either is called. <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
<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 f! (n!) IF n = 0 THEN
m = 0
ELSE
m = f(m(n - 1))
END IF END FUNCTION</lang>
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>
.
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>
AutoHotkey
<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>
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 explicity, 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>
/* 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(int n); int M(int n);
int F(int n) {
if ( n==0 ) return 1; return n - M(F(n-1));
}
int M(int n) {
if ( n == 0 ) return 0; return n - F(M(n-1));
}
int main() {
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 0;
}</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>
- include <vector>
- 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>
Clojure
<lang clojure> (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>
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> long male (long n) { if (n) return n - female (male (n - 1)); else return 0; }
long female (long n) { if (n) return n - male (female (n - 1)); else return 1; } </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>
FALSE
[$[$1-f;!m;!-1-]?1+]f: [$[$1-m;!f;!- ]? ]m: [0[$20\>][\$@$@!." "1+]#%%]t: f; t;!" "m; t;!
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 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)
<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>
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>
J
F =: 1:`(- M @ $: @ <:) @.* M =: 0:`(- F @ $: @ <:) @.*
Java
<lang java5>public static int f(int n) {
if ( n == 0 ) return 1; return n - m(f(n - 1));
}
public static int m(int n) {
if ( n == 0 ) return 0; return n - f(m(n - 1));
}
public static void main(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));
}
out = {F: [], M: []}; for (var 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
Logo
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>
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>
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
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 <objc/Object.h>
@interface Hofstadter : Object + (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>
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>
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>use strict;
sub F {
my $n = shift; return 1 if $n==0; return $n - M(F($n-1));
}
sub M {
my $n = shift; return 0 if $n==0; return $n - F(M($n-1));
}
my @ra = (); my @rb = (); for(my $i=0; $i < 20; $i++) {
push @ra, F($i); push @rb, M($i);
} print join(" ", @ra) . "\n"; print join(" ", @rb) . "\n";</lang>
<lang perl> sub F {!$_[0] or $_[0] - M(F($_[0]-1))} sub M {$_[0] and $_[0] - F(M($_[0]-1))}
for my $f (\&F, \&M)
{print "@{[map $f->($_), 0..20]}\n"}
</lang>
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>
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>
<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>
Python
.
<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>
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).
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.
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>
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
).
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
Define F(n) = when(n=0, 1, n - M(F(n - 1))) Define M(n) = when(n=0, 0, n - F(M(n - 1)))
UNIX 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 understood 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 in other domains.)
<lang Ursala>
- import std
- import nat
- import sol
- 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
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>