Иванова Г.С., Ничушкина Т.Н.
Конспект лекций
по курсу "Алгоритмические языки и программирование".
Тема "Рекурсия". Глава 1. Рекурсия. Основные положения.
1.1. Рекурсивные алгоритмы.
Строгое определение некоторых понятий может опираться на то же понятие. Существует доступная математическая форма определений, согласно которой определяемое понятие используется как заголовок определения и как его элемент. Эта форма называется рекурсивной или индуктивной.
Рекурсия является особенно мощным средством в математических определениях. Известны примеры рекурсивных определений натуральных чисел, древовидных структур и некоторых функций.
Пример 1. Определение отношения "Кубик А находится в башне над кубиком В."
башне над кубиком В.
2. Если кубик А лежит непосредственно на кубике С и этот кубик находится в
башне над кубиком В, то кубик А находится в башне над кубиком В.
Первое утверждение носит название базисного. Базисное утверждение нерекурсивно.
Рис. 1
Второе утверждение носит название рекурсивного или индуктивного. Оно строится так, чтобы полученная в результате повторных применений цепочка определений редуцировалась к базисному утверждению.
При этом базисное утверждение определяет один или более случаев, удовлетворяющих определению, а рекурсивное утверждение показывает, как надо применять определение, чтобы проверить, удовлетворяют ли ему другие случаи.
Применительно к примеру, это выглядит следующим образом. Если требуется определить, находится ли синий кубик в башне над зеленым, то необходимо действовать следующим образом:
а) Проверяем первое утверждение "Синий кубик находится в башне над зеленым, если он лежит на зеленым". Оно ложно, следовательно, переходим к проверке второго.
б) Второе утверждение "Синий кубик находится в башне над зеленым, если синий кубик лежит на красном, а красный находится в башне над зеленым" требует доказательства того, что красный кубик находится в башне над зеленым. А это значит, что надо вновь применить правило 1 и проверить, находится ли красный кубик непосредственно на зеленом. Поскольку это положение истинно, значит истинно и то, что синий кубик находится в башне над зеленым.
Пример 2. Рекурсивное определение понятия "нечетное число".
Базисное утверждение: Число 1 является нечетным.
Рекурсивное утверждение: Если i является нечетным числом, то нечетными являются и числа i-2 и i+2.
Определить, являются ли числа 7 и -7 нечетными.
а) 7-2 -> 5 5-2 -> 3 3-2 -> 1 1 - нечетное число, следовательно, число 7 - нечетное.
б) -7+2 -> -5 -5+2 -> -3 -3+2 -> -1 -1+2 -> 1 - нечетное число, следовательно, число -7 - нечетное.
Очень важной областью применения рекурсии является синтаксис языков программирования.
Пример 3. Определение целой константы.
Базисное утверждение: Числа от 0 до 9 являются целыми константами.
Рекурсивное утверждение: Добавление десятичной цифры к записи целой константы образует новую целую константу.
Соответствующая форма Бэкуса-Наура записывается следующим образом:
<цифра>:: = 0|1|2|3|4|5|6|7|8|9 - базис
<целая константа>:: =<цифра>|<целая константа> - рекурсивная часть
Таким образом, мощность рекурсии заключается в том, что она позволяет определить бесконечное множество объектов с помощью конечного количества высказываний.
В программировании рекурсия используется как при определении структур данных, так и при разработке алгоритмов.