Косвенная (взаимная) рекурсия
Back Home Up Next

Циклическая последовательность вызовов нескольких функций 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

Однако при подобных преобразованиях не стоит забывать, что во многих случаях совокупности функций с взаимной рекурсией оказываются более обозримыми и легче читаемыми, чем равнозначные им системы с прямой рекурсией.

Home Содержание Схемы ООД Доска объявлений Поиск