Рекурсия является одним из удобнейших средств при работе с линейными списками. Она позволяет сократить код программы и сделать алгоритмы обхода узлов деревьев и списков более понятными.
По определению понятия, рекурсивная процедура - это процедура, в теле которой есть обращение к самой себе. Для того, чтобы процесс рекурсии не стал бесконечным и не вызвал переполнение стека, в каждой рекурсивной процедуре должен быть определен ограничитель рекурсии, блокирующий дальнейшее «размножение» тела процедуры.
Хотя рекурсии в списках не являются настолько очевидным решением, как в деревьях, все же они позволяют оптимизировать обработку линейных списков. В списках возможны два варианта прохода: из начала в конец и из конца в начало. Эти методы реализуются очень легко в случае с двунаправленными списками.
Рекурсию в линейных списках демонстрирует следующий пример: подсчет числа элементов в линейном однонаправленном списке.
Procedure Count_El (var q : El; var count : integer);