Циклическая последовательность вызовов нескольких функций F1, F2, …, Fk (процедур, алгоритмов) друг друга: F1 вызывает F2, F2 вызывает F3, …, Fk вызывает F1 (k>1), называют косвенной или взаимной рекурсией. Ограничимся рассмотрением одного примера (язык - Qbasic, символ “\” - знак операции целочисленного деления). Головная программа
DECLARE FUNCTION g1! (n) DECLARE FUNCTION g0! (n) CLS INPUT "Введите целое n ? ", n PRINT g0(n) |
для целого неотрицательного n, обращаясь к взаимно-рекурсивным функциям g0(n) и g1(n), подсчитывает и возвращает логическое значение, равное 1 (истина), если в двоичном представлении n имеется четное число цифр “1”, и 0 (ложь) в противном случае.
FUNCTION g0 (n) IF n = 0 THEN z = 1 ELSEIF (n MOD 2) = 0 THEN z = g0(n \ 2) ELSE z = g1(n \ 2) END IF g0 = z END FUNCTION |
FUNCTION g1 (n) IF n = 0 THEN z = 0 ELSEIF (n MOD 2) = 0 THEN z = g1(n \ 2) ELSE z = g0(n \ 2) END IF g1 = z END FUNCTION |
Иногда косвенную рекурсию удается свести к обычной рекурсии. Например, в нашем случае можно было бы перейти к линейной рекурсии, заменив функции g0(n) и g1(n) функцией g2 (n):
DECLARE FUNCTION g2! (n) CLS INPUT "Введите целое n ? ", n PRINT g2(n) |
FUNCTION g2 (n) IF n = 0 THEN g2 = 1 ELSEIF (n MOD 2) = 0 THEN g2 = g2(n \ 2) ELSE g2 = 1 - g2(n \ 2) END IF END FUNCTION |
Однако при подобных преобразованиях не стоит забывать, что во многих случаях совокупности функций с взаимной рекурсией оказываются более обозримыми и легче читаемыми, чем равнозначные им системы с прямой рекурсией.