На этом шаге мы рассмотрим взаимную рекурсию.
- Определение.
-
- (1) Взаимной рекурсией называется рекурсия, в которой две или более функций вызывают друг друга.
- (2) Взаимно-рекурсивными функциями называют функции, вызывающие друг друга "по цепочке" (другими словами, функция вызывает другуюфункцию 1, 0 а та, в свою очередь, вызывает первую).
Приведем пример такой рекурсии.
-- Демонстрация взаимной рекурсии на примере функций -- определения чётности неотрицательного целого числа ----------------------------------------------------- isEven:: Int -> Bool isEven 0 = True isEven n = isOdd (n-1) ---------------------- isOdd:: Int -> Bool isOdd 0 = False isOdd n = isEven (n-1) ------------------------------ -- Неудачные тестовые примеры: -------------------------------------------- test = isEven 0 && isEven 2 && isEven 1024 && isOdd 1 && isOdd 3 && isOdd 1025 && not (isEven 1) && not (isEven 255) && not (isOdd 2) && not (isOdd 256)
На следующем шаге мы рассмотрим рекурсию высших порядков.
