Mutual Recursion
The Subprograms are mutually recursive if they directly or indirectly call each other. In the illustration below, the Boolean functions odd & even, that determine whether the number is odd or even, call each other straightly. The forward declaration of odd is essential as even calls odd, that is not yet declared when the call is made.
FUNCTION odd (n NATURAL) RETURN BOOLEAN; -- forward declaration
FUNCTION even (n NATURAL) RETURN BOOLEAN IS
BEGIN
IF n = 0 THEN
RETURN TRUE;
ELSE
RETURN odd(n - 1); -- mutually recursive call
END IF;
END even;
FUNCTION odd (n NATURAL) RETURN BOOLEAN IS
BEGIN
IF n = 0 THEN
RETURN FALSE;
ELSE
RETURN even(n - 1); -- mutually recursive call
END IF;
END odd;
When the positive integer n is agreed to odd or even, the functions call each other by turns. At each call, the n is decremented. Eventually, n becomes zero and the final call returns TRUE or FALSE. For illustration, passing the number 4 to odd outcome in this series of calls:
odd(4)
even(3)
odd(2)
even(1)
odd(0) -- returns FALSE
On the other hand, passing the number 4 to even outcome in this series of calls:
even(4)
odd(3)
even(2)
odd(1)
even(0) -- returns TRUE