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:










F
(
0
)



=
1
 
;
 
M
(
0
)
=
0




F
(
n
)



=
n
−
M
(
F
(
n
−
1
)
)
,

n
>
0




M
(
n
)



=
n
−
F
(
M
(
n
−
1
)
)
,

n
>
0.






{\displaystyle {\begin{aligned}F(0)&=1\ ;\ M(0)=0\\F(n)&=n-M(F(n-1)),\quad n>0\\M(n)&=n-F(M(n-1)),\quad n>0.\end{aligned}}}





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




MODULE MutualRecursion;
FROM InOut IMPORT WriteCard, WriteString, WriteLn;
 
TYPE Fn = PROCEDURE(CARDINAL): CARDINAL;
 
PROCEDURE F(n: CARDINAL): CARDINAL;
BEGIN
    IF n=0 THEN RETURN 1;
    ELSE RETURN n-M(F(n-1));
    END;
END F;
 
PROCEDURE M(n: CARDINAL): CARDINAL;
BEGIN
    IF n=0 THEN RETURN 0;
    ELSE RETURN n-F(M(n-1));
    END;
END M;
 
(* Print the first few values of one of the functions *)
PROCEDURE Show(name: ARRAY OF CHAR; fn: Fn);
    CONST Max = 15;
    VAR i: CARDINAL;
BEGIN
    WriteString(name);
    WriteString(": ");
    FOR i := 0 TO Max DO
        WriteCard(fn(i), 0);
        WriteString(" ");
    END;
    WriteLn;
END Show;
 
(* Show the first values of both F and M *)
BEGIN
    Show("F", F);
    Show("M", M);
END MutualRecursion.