Виды рекурсивных структур данных

Арифметические выражения

 

При описании арифметических выражений рекурсия означает возможность вложенности, т.е. использование в выражениях в качестве операндов подвыражений, заключенных в круглые скобки. Синтаксис языков программирования принято описывать с помощью рекурсивной нотации, называемой формой Бэкуса-Наура (БНФ). Она состоит из правил подстановки, определяющих как нетерминальный символ (т.е. символ, требующий дальнейшего уточнения) может быть замещен другим нетерминальным или терминальным символом (т.е. символом, не требующим уточнения). В правилах подстановки используется знак  “|” для разделения альтернативных подстановок. Нетерминальные символы заключаются в угловые скобки “<>”. Символ “::=” означает “это есть”.

Определение простейшего арифметического выражения с помощью БНФ выглядит следующим образом:

 

 <арифметическое выражение>::= < операнд> <знак операции> < операнд>

  <операнд>:: = <идентификатор> | (<арифметическое выражение>)

 <знак операции>:: = + | - | * | /

 <идентификатор>:: =  a | b | …| z | A | B | … | Z

 

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

Примеры простейших арифметических выражений, соответствующих данному определению:  X+Y X * (Y + Z) (Y * Z) – X (X + Y) * (Z – W)

(X / (Y + Z)) * W  и т.п.

Динамические линейные структуры данных: списки

 

Рекурсивное определение списка: список - это пустая структура или структура, состоящая из особого элемента (первого или головного) и списка. Рекурсивную интерпретацию линейного односвязного списка иллюстрирует рис. 61.

                                           

                                                 

Рис. 61. Рекурсивная интерпретация списка

 

Как следует из рекурсивного определения списка, условием завершения его обработки является достижение пустого списка в процессе применения шагов рекурсии.

Рассмотрим две рекурсивные процедуры, одна из которых распечатывает содержимое информационных полей линейного односвязного списка в прямом порядке (Print_Front), а вторая – в обратном порядке (Print_Back).

 

Procedure Print_Front(first: PList);	{ распечатка содержимого списка }
Begin	{ в прямом направлении }
If first <> nil then begin
writeln(first^.info);
Print_Front(first^.link)	{ задняя рекурсия (см. ниже) }
end;
end;

 

Procedure Print_Back(first: PList);	{ распечатка содержимого списка }
begin	{ в обратном направлении }
if first <> nil then begin
Print_Back(first^.link)
writeln(first^.info);
end;
End;