Основы рекурсии

  По одной из классификаций языки программирования делятся на процедурные, называемые также операторными или императивными, и декларативные языки. Подавляющее большинство используемых в настоящее время языков программирования, например Бейсик, Кобол, Фортран, Паскаль, Си и Ада, относятся к процедурным языкам. Наиболее существенными классами декларативных языков являются функциональные, или аппликативные, и логические языки. К категории функциональных языков относятся, например Лисп, FP, Apl, Nial, Krc и Logo. Самым известным языком логического программирования является Пролог.

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

  Процедурная программа состоит из операторов и предложений, управляющих их выполнению. Типичными операторами являются операторы присваивания и передачи управления, операторы ввода-вывода и специальные предложения для организации циклов. Из них можно составлять фрагменты программ и подпрограммы. В основе такого программирования лежат взятие значения какой-то переменной, совершение над ним действия и сохранение нового значения с помощью оператора присваивания, и так до тех пор пока не будет получено (и, возможно, напечатано) желаемое окончательное значение.
  Функциональная программа состоит из совокупности определений функций. Функции, в свою очередь, представляют собой вызовы других функций и предложений, управляющих вызовами. Вычисления начинаются с вызова некоторой функции, которая в свою очередь вызывает функции, входящие в её определение и т.д. в соответствии с иерархией определений и структурой условных предложений. Функции часто либо прямо, либо опосредованно вызывают сами себя.
  Каждый вызов возвращает некоторое значение в вызвавшую его функцию, вычисление которой после этого продолжается; этот процесс повторяется до тех пор пока запустившая вычисления функция не вернёт конечный результат пользователю.
  "Чистое" функциональное программирование не признаёт присваиваний и передач управления. Разветвление вычислений основано на механизме обработки аргументов условного предложения. Повторные вычисления осуществляются через рекурсию, являющуюся основным средством функционального программирования.

  Многие практические ситуации предполагают рекурсивное или самоповторяющееся поведение, возвращающееся к самому себе. Предположим, что мы, например, пытаемся прочитать текст на другом языке, пользуясь толковым словарём этого языка. Когда в тексте встречается незнакомое слово, то его объяснение ищется в словаре. В объяснении слова могут, в свою очередь, встретится незнакомые слова, которые нужно найти в словаре и т.д. Эту процедуру можно определить с помощью следующих правил:

1. Найди слово в словаре.
2. Прочитай статью, объясняющую значение этого слова.
3. Если объяснение понятно, т.е. статья не содержит непонятных слов, продолжи чтение с последнего прерванного места.
4. Если в объяснении встречается незнакомое слово, то прекрати чтение, запомни место прекращения и выясни значение слова, придерживаясь совокупности правил "Выяснение значения слова".

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

  В рекурсивном описании действий имеет смысл обратить внимание на следующие обстоятельства. Во-первых, процедура содержит как правило терминальные ветви и условие окончания. Во-вторых, когда процедура доходит до рекурсивной ветви, то функционирующий процесс приостанавливается и новый такой же процесс запускается с начала, но уже на новом уровне. Прерванный процесс каким-нибудь образом запоминается. Он будет ждать и начнёт исполняться лишь после окончания нового процесса. В свою очередь, новый процесс может приостановиться, ожидать и т.д.
  Так образуется как бы дерево прерванных процессов, из которых выполняется лишь последние в настоящий момент времени процессы (листочки); после окончания их работы продолжает выполняться предшествовавший им процесс. Целиком весь процесс выполнен, когда дерево снова опустеет, или, другими словами, все прерванные процессы выполнятся.

  В реальном мире рекурсия проявляется в виде различных форм и связей. Она может быть как в структуре, так и в действиях.
  Каждому известно изображение, повторяющееся в двух зеркалах, установленных друг против друга, картина, изображающая картину, телевизор, в котором виден телевизор, и т.д. В математике рекурсия встречается в связи с многими различными аспектами, такими как ряды, повторяющиеся линии, алгоритмы, процедуры определения и доказательства, одним словом, в самых различных структурах.
  Рекурсия встречается обычно и в природе: деревья имеют рекурсивное строение (ветки образуются из других веток), реки образуются из впадающих в них рек. Клетки делятся рекурсивно. В растениях это часто видно уже на макроуровне. Например, семенная чешуя шишек и семена некоторых цветов (например, подсолнечника) часто расположены пересекающимися спиралевидными веерами, определяемыми соотношением чисел Фибоначчи.
  Продолжение жизни связано с рекурсивным процессом. Молекулы ДНК и вирусы размножаются, копируя себя, живые существа имеют потомство, которое, в свою очередь, тоже имеет потомство и т.д.
  Рекурсия распространена и в языке, и в поведении так же, как в способах рассуждения и познания. Рекурсия в языке, например, может быть в структуре или в содержании:

"Петя сказал, что Вася сказал, что …"
"Знаю, что знаю, но не помню"
"Сделать; заставить сделать; заставить, чтобы заставили сделать; …"
"Замени x этим предложением"
"Запомни и передай это сообщение"
…

  Музыкальные формы и действия также могут быть рекурсивными во многих отношениях (например, канон, в котором мелодия сопровождается той же мелодией с задержкой, и другие).
  Целенаправленное поведение и решение проблем являются рекурсивными процессами. Точно так же и исследования в области искусственного интеллекта рекурсивны в своей попытке исследовать процессы, протекающие в головном мозге, при помощи которых происходит исследование и решение проблем, в том числе и исследования в области искусственного интеллекта.

  Рекурсия в Лиспе основана на математической теории рекурсивных функций. Рекурсия хорошо подходит для работы со списками, так как сами списки могут состоять из подсписков, т.е. иметь рекурсивное строение. Для обработки рекурсивных структур совершенно естественно использование рекурсивных процедур.
  Списки можно определить с помощью следующих правил Бэкуса-Наура:

  Рекурсия есть как в определении головы, так и в определении хвоста списка. Заметим, что приведённое выше определение напрямую отражает определения функций, работающих со списками, которые могут обрабатывать рекурсивным вызовом голову списка, т.е. "в глубину" (в направлении first), и хвост списка, т.е. "в ширину" (в направлении rest).
  Списки можно определить и в следующей форме, которая подчёркивает логическую рекурсивность построения списков и атомов и подсписков:

  В программировании на Лиспе рекурсия используется для организации повторяющихся вычислений. На ней же основано разбиение проблемы и разделение её на подзадачи, решение которых, насколько это возможно, пытаются свести к уже решённым или в соответствии с основной идеей рекурсии к решаемой в настоящий момент задаче.
  На рекурсии основан и часто используемый при решении задач и при поиске механизм возвратов, при помощи которого можно вернуться из тупиковой ветви к месту разветвления, аннулировав проделанные вычисления. Рекурсия в Лиспе представляет собой не только организацию вычислений - это образ мыслей и методология решения задач.

  Теория рекурсивных функций наряду с алгеброй списков и лямбда-исчислением является ещё одной опорой, на которой покоится Лисп. В этой области математики изучаются теоретические вопросы, связанные с вычислимостью. Под вычислимыми понимаются такие задачи, которые в принципе можно запрограммировать и решить с помощью вычислительной машины. Теория рекурсивных функций предлагает наряду с машиной Тьюринга, лямбда-исчислением и другими теоретическими формализмами эквивалентный им формализм алгоритмической вычислимости.
  В теории рекурсивных функций сами функции (алгоритмы) и их свойства рассматриваются и классифицируются в соответствии с тем, какие функции можно получить и вычислить, используя различные формы рекурсии. Основная идея рекурсивного определения заключается в том, что функцию можно с помощью рекуррентных формул свести к некоторым начальным значениям, к ранее определённым функциям или к самой определяемой функции, но с более "простыми" аргументами. Вычисление такой функции заканчивается в тот момент, когда оно сводится к известным начальным значениям. Например, числа Фибоначчи

  0, 1, 1, 2, 3, 5, …

используя инфиксную нотацию Лиспа, можно определить с помощью следующих рекуррентных формул:

  (0 fib) = 0
  (1 fib) = 1
  (n fib) = (((n - 1) fib) + ((n - 2) fib))

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

  (0 Ack x y) = (y + x)
  (1 Ack x y) = (y * x)
  (2 Ack x y) = (y ^ x)
  …

  ((z + 1) Ack x y) =

к значениям y x-1 раз применяется операция (lambda (u v) (z Ack u v))

  Заданная с помощью приведённой выше схемы функция Ack не является примитивно рекурсивной, хотя она и вычислимая, т.е. её можно определить и на основе этого определения вычислить её значение за конечное время.
  Можно показать, что существуют функции, значения которых можно вычислить с помощью алгоритма, но которые нельзя алгоритмически описать. Вычисление такой функции может быть бесконечным. В качестве примера приведём функцию (n f m), результатом которой является 1 в случае, если в десятичной записи числа π встречается фрагмент из повторяющихся цифр m длиной n.
  Можно показать, что алгоритм вычисления этой функции существует, но нам неизвестно, каков он. Мы можем лишь пытаться вычислять знаки π в надежде, что искомый фрагмент обнаружится, но определить, закончится ли когда-нибудь вычисление, мы не можем. Такие функции называются общерекурсивными.
  Класс примитивно рекурсивных функций достаточно интересен с точки зрения многих практических проблем. Применение рекурсивных функций в Лиспе не ограничивается лишь численными аргументами, они используются(и даже в первую очередь) для символьных структур, что открывает новые большие возможности по сравнению с численными вычислениями.