Mutual recursion: Difference between revisions
m (Added to recursion cat) |
(fortran) |
||
Line 51: | Line 51: | ||
return 0; |
return 0; |
||
}</lang> |
}</lang> |
||
=={{header|Fortran}}== |
|||
As far as the code of the two function 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, e.g. by using a "<tt>use</tt>" (we do that if M and F function are inside different modules) |
|||
{{works with|Fortran|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 <tt>pure</tt> so that we can use them in a <tt>forall</tt> 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> |
|||
=={{header|Java}}== |
=={{header|Java}}== |
Revision as of 22:52, 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).
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 function 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, 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>
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).