Рекурсивные запросы
В этой главе…
- Управление рекурсией
- Как определять рекурсивные запросы
- Способы применения рекурсивных запросов
SQL-92 и более ранние версии часто критиковали за отсутствие реализации рекурсивной обработки. Многие важные задачи, которые трудно решить другими средствами, легко решаются с помощью рекурсии. В SQL: 1999 появились расширения, позволяющие создавать рекурсивные запросы. Благодаря этим расширениям мощь языка SQL существенно возрастает. Если ваша реализация SQL включает в себя расширения для рекурсии, то вы можете эффективно решать новый большой класс задач. Впрочем, в основной части стандарта SQL:2003 поддержка рекурсии не предусмотрена. Поэтому во многих используемых реализациях этой поддержки может и не быть.
Что такое рекурсия
Это довольно старая возможность таких языков программирования, как Logo, LISP и C++. В этих языках можно определить функцию (совокупность одной или множества команд), которая выполняет заданную операцию. Главная программа вызывает функцию, выполняя для этого команду, которая называется вызовом функции. В процессе своей работы функция вызывает сама себя – это самая простая форма рекурсии.
Для иллюстрации достоинств и недостатков рекурсии приведем простую программу, в которой одна из функций использует рекурсивные вызовы. Эта программа, написанная на C++, чертит на экране компьютера спираль, начиная с единичного сегмента, направленного вверх.
В ее состав входят три функции.
- Функция line(n) чертит отрезок длины n.
- Функция Jeft_turn(d) поворачивает "чертежный инструмент" на d градусов против часовой стрелки.
- Функция spiral(segment), которая определяется следующим образом:
void spiral(int segment) { line(segment); left_turn(90); spiral(seement + 1); }
Если из главной программы вызвать spiral(1), то будут выполняться такие действия:
- spiral(1) чертит единичный отрезок (т.е. единичной длины), направленный вверх;
- spiral(1) выполняет поворот на 90 градусов против часовой стрелки;
- spiral(1) вызывает spiral(2);
- spiral(2) чертит отрезок, равный по длине двум единичным и направленный влево;
- spiral(2) выполняет поворот на 90 градусов против часовой стрелки;
- spiral(2) вызывает spiral(3);
- и т.д.
Постепенно благодаря программе появляется спиральная кривая, изображенная на рис. 12.1.
Рис. 12.1. Результат вызова spiral(1)