Глава 1. Раздел 4.3. Рекурсия

1.4.3. РЕКУРСИЯ

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

Необходимость в рекурсивных определениях обычно возникает в тех случаях, когда функция должна быть определена для бесконечного множества аргументов и при этом размер аргумента может быть произвольно большим.

Рассмотрим, например, следующую задачу. Пусть требуется определить функцию Reverse, которая "переворачивает" выражение, т.е. переставляет термы аргумента в обратном порядке. А именно, если на вход поступает объектное выражение вида

Ot1 Ot2 ... Otn

где Ot1, Ot2, ..., Otn - некоторые объектные термы, то на выходе должно получиться объектное выражение

Otn ... Ot2 Ot1

Если бы длина входного выражения была ограничена, например, если бы мы знали, что n<=3, можно было бы разобрать четыре разных случая и написать следующее определение функции:


	$func Reverse e.Exp = e.Exp;
	Reverse
	{
	= ;
	t1 = t1;
	t1 t2 = t2 t1;
	t1 t2 t3 = t3 t2 t1;
	};

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

Можно, однако, преодолеть это затруднение с помощью рекурсии. В данном случае можно рассуждать следующим образом. Рассмотрим входное выражение

Ot1 Ot2 ... Otn

Если n=0, то результатом должно быть пустое выражение. Если же n>=1, то можно свести исходную задачу к более простой: отбросить первый терм входного выражения, получив выражение длины n-1,

Ot2 ... Otn

и перевернуть это более короткое выражение. Получится

Otn ... Ot2

Теперь ясно, что если к этому выражению приписать справа Ot1, мы как раз и получим желаемый результат

Otn ... Ot2 Ot1

Эти рассуждения приводят нас к следующему рекурсивному определению функции Reverse :


	Reverse
	{
	= ;
	t.X e.Rest = <Reverse e.Rest> t.X;
	};

Интересно отметить, что для задачи переворачивания выражения существует и другое решение, которое ничем не хуже первого: чтобы свести задачу к более простой, можно было бы отбросить не первый терм, а последний. Тогда получилось бы следующее решение


	Reverse
	{
	= ;
	e.Rest t.X = t.X <Reverse e.Rest>;
	};

Нетрудно заметить также, что в действительности сущность решения состоит в том, что мы разбиваем исходное выражение Oe на два непустых выражения Oe1 и Oe2 меньшего размера, таких, что

Oe = Oe1 Oe2

Теперь мы можем перевернуть каждое из выражений Oe1 и Oe2 по отдельности. Пусть при этом получатся выражения Oe1' и Oe2' соответственно. Тогда ясно, что

Oe2' Oe1'

равно результату обращения исходного выражения Oe.

Если Рефал реализован на многопроцессорной машине таким образом, что обращение выражений Oe1 и Oe2 можно выполнять одновременно, оказывается, что выгодно, чтобы Oe1 и Oe2 были приблизительно одинаковой длины. Тогда получаем следующий вариант описания функции, в котором используются библиотечные функции из модулей ACCESS и ARITHM:


	$func Reverse e.Exp = e.Exp;
	Reverse
	{
	= ;
	t1 = t1;
	eX,
	<Length e.X> :: sLen,
	<Div sLen 2> :: sDiv,
	= <Reverse <Middle sDiv 0 eX>>
	<Reverse <Left 0 sDiv eX>>;
	};