На этом шаге мы введем понятие рекурсии.
В "чистом" функциональном языке LISP нет ни циклических предложений (LOOP), ни тем более операторов передачи управления. Для программирования повторяющихся вычислений в нем используются лишь функции COND и определения рекурсивных функций.
В [1,с.66-67] можно прочесть следующее неформальное разъяснение сути процесса рекурсии: под рекурсией понимаем такую организацию сложной системы, при которой: выделяется некоторый набор базовых подсистем; система способна в процессе функционирования создавать неограниченное количество копий базовых систем, осуществлять взаимодействие между ними и уничтожать их; функционирование системы состоит из функционирования базовых подсистем и их активных копий; при вызове копии допустимо ее изменение, определяемое ситуационной обстановкой в момент вызова.
Мы будем понимать под рекурсивной функцией функцию, в теле которой присутствует вызов себя самой.
Итеративные и рекурсивные программы теоретически одинаковы по своим вычислительным возможностям, иными словами, множества вычислимых с их помощью функций совпадают. Так что любое вычисление в принципе, можно запрограммировать любым из этих способов. Однако свойства итеративных и рекурсивных вариантов программ могут существенно отличаться. В связи с этим часто приходится решать, какой из способов программирования больше подходит для данной задачи. От сделанного выбора зависит простота и естественность программирования, а также его эффективность с точки зрения времени исполнения и использования памяти.
С помощью итеративного программирования, как правило, более длинного и трудного в осуществлении, результат может вычисляться значительно проще и быстрее. Это происходит по двум причинам:
- во-первых, потому, что компьютеры фон-неймановской архитектуры в общем ориентированы на последовательные вычисления, и,
- во-вторых, потому что трансляторы не всегда в состоянии преобразовать рекурсивное определение в итеративное и используют при вычислениях стек, несмотря на то, что он не всегда нужен.
Рекурсивное программирование является в общем более коротким и содержательным. Особенно полезно использовать рекурсию в тех случаях, когда решаемая задача или обрабатываемые данные по сути своей рекурсивны.
Рекурсию очень хорошо иллюстрировать на примере работы со списками, так как сами списки имеют рекурсивное строение.
В самом деле, вспомним, что ранее (шаг 4. Список как фундаментальный тип данных) мы определили список с помощью следующих правил Бэкуса-Наура: список либо пуст, либо это точечная пара, хвост которой является списком. Рекурсия в определении налицо!
Рекурсивными функциями можно с успехом пользоваться при работе с другими динамическими структурами данных (например, деревьями), имеющими рекурсивную организацию.
Рекурсия отражает существенную черту абстрактного мышления, проявляющуюся при анализе
сложных алгоритмических и структурных конструкций в самых различных приложениях. Дело
в том, что, пользуясь рекурсией, мы избавляемся от необходимости утомительного последовательного
описания конструкции и ограничиваемся лишь выявлением взаимосвязей между различными
уровнями этой конструкции. Рекурсия в языке LISP представляет собой не только
организацию вычислений - это образ мышления и методология решения задач.
(1)Анисимов А.В. Информатика. Творчество. Рекурсия. - Киев: Наук.думка, 1988. - 224 с.
На следующем шаге мы рассмотрим, как создавать рекурсивные определения.
