Конспект установочных лекций по комплексному курсу Информатика, Теория информации
Индуктивное толкование рекурсивных объявлений функций
Рекурсивные объявления встречаются во многих областях информатики. Уже описание формальных языков с помощью объявлений нетерминальных вспомогательных обозначений в виде БНФ-выражений представляет пример рекурсии. Заметим, что рекурсия встречается не только в ЯП при рекурсивных объявлениях вычислительных предписаний, но также и в других областях. Один из примеров рекурсии образуют системы БНФ-определений для нетерминалов, которые снова встречаются в правой части определения.
