Mutual recursion: Difference between revisions
(perl (v0)) |
(php) |
||
Line 209:
print join(" ", @ra) . "\n";
print join(" ", @rb) . "\n";</lang>
=={{header|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>
=={{header|Python}}==
|
Revision as of 23:46, 9 April 2009
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).
AWK
In AWK too it is enough both functions are defined before they are really 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>
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 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>
Fortran
As far 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>
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>
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 "usage". (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>
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).
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>