Рекурсивные запросы
Маленькие трудности
Ну ладно. Здесь ситуация не такая серьезная, как с Аполлоном-13, когда на пути к Луне прорвало его главный кислородный бак. Но и мы тоже испытываем трудности: наша маленькая программа от нас "убегает". Она все продолжает и продолжает вызывать сама себя и чертит все большие и большие отрезки. Программа будет делать это до тех пор, пока компьютер, пытающийся ее выполнить, не исчерпает свои ресурсы и не выведет на экран сообщение об ошибке. А если вам не повезет, то компьютер просто зависнет.
Сбой недопустим
Такой сценарий развития событий показывает одну из опасностей, связанных с использованием рекурсии. Программа, написанная для того, чтобы обращаться к себе самой, вызывает на выполнение свой новый экземпляр, а тот, в свою очередь, вызывает еще один, и так до бесконечности. Обычно это не то, что нужно. Чтобы решить проблему, программисты помешают в рекурсивную функцию условие завершения – предел того, насколько глубоко должна зайти рекурсия. В результате программа выполняет нужные действия, а затем красиво завершается. Условие завершения мы можем поместить и в нашу программу черчения спиралей, чтобы сберечь ресурсы компьютера и избежать головокружения у программистов:
void spiral2(int segment)
{
if (segment <= 10)
{
line(segment);
left_turn(90),
spiral2(segment+ 1);
}
}
При вызове программа spiral2(l) выполняется и затем рекурсивно вызывает сама себя до тех пор, пока значение segment не превысит 10. Как только значение segment станет равным 11, конструкция if (segment <= 10) возвратит значение False, и код, находящийся во внутренних скобках, будет пропущен. Управление снова передается предыдущему вызову spiral2(l), а оттуда постепенно возвращается к самому первому вызову, после которого программа завершается.
Каждый раз, когда функция вызывает саму себя, она еще на один уровень удаляется от главной программы – места начала операции. Чтобы эта главная программа продолжила работу, самая последняя итерация (т.е. повторение выполнения) должна вернуть управление предпоследней – той, которая ее вызвала. Предпоследняя итерация обязана поступить точно так же, и процесс продолжается, пока управление не вернется в главную программу, в которой был сделан первый вызов рекурсивной функции.
Рекурсия – это мощный инструмент для повторного выполнения кода. Она идеально подходит для поиска в древовидных структурах, например, в файловых системах, сложных электронных схемах или многоуровневых распределенных сетях.
Что такое рекурсивный запрос
Рекурсивным называется запрос, который функционально зависит от себя самого. Самой простой формой такой функциональной зависимости является случай, когда внутри оператора запроса Q1 находится вызов этого же запроса. Более сложный случай будет тогда, когда запрос Q1 зависит от запроса Q2, который, в свою очередь, зависит от Q1. И сколько бы запросов ни находилось между первым и вторым вызовом одного и того же запроса, главное, чтобы имела место функциональная зависимость.