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>
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>
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 has no 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>
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. <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 apparently we don't need pre-declaration (like C) when "encapsulating" the functions as static (class) methods.
<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>
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>
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>
Haskell
<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>
Java
<lang java5>public static int f(int n) {
if ( n == 0 ) return 1; return n - m(f(n - 1));
}
public 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>
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>
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 is the way to "say" OCaml that the functions call themselves (rec) and each others (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>
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>
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).
Scheme
Could probably be optimized with tail recursion. <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>
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>
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>
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 x86> 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>