Косвенная рекурсия, пример

При взаимной (неявной или косвенной) рекурсии функция содержит обращение к себе через цепочку вызовов других процедур. Определение такой рекурсивной функции состоит из определений как минимум двух функций: определения самой рекурсивной функции, содержащей вызов другой (вспомогательной) функции и определения вспомогательной функции, содержащей вызов определяемой (рекурсивной) функции. Отметим, что эта вспомогательная функция

является также взаимно рекурсивной. Рассмотрим в качестве примера следующую задачу. Определить предикат, проверяющий, содержит ли список четное число элементов на верхнем уровне, и предикат, проверяющий список на нечетность числа элементов. Декларативное описание задачи следующее:

 пустой список четный;

 у четного списка нечетный хвост;

 у нечетного списка четный хвост

ЛИСП: >(defun even1 (l)

(cond

((null l) t); пустой список четный

(t (number1 (cdr l))))); у четного списка нечетный хвост

EVEN1

>(defun number1 (l)

(cond

((null l) nil); пустой список − не нечетный

(t (even1 (cdr l))))); у нечетного списка четный хвост

NUMBER1

>(even1 ‘(1 2 3 4))

T

>(even1 ‘(1 2 3))

NIL

>(number1 ‘(1 2 3 4))

NIL

>(number1 ‘(1 2 3))

T

На Эрланге следующее определение:

even1(L) when L==[] -> true;

even1([_|T]) -> number1(T).

number1(L) when L==[] -> false;

number1([_|T]) -> even1(T).

1> recc:even1([1,2,3]).

false

2> recc:even1([1,2,3,4]).

true

3> recc:number1([1,2,3,4]).

False

Дата добавления: 2015-07-19