Лекция 12. Рекурсия

Лекция 12. Рекурсия

Рекурсия. Стек. Создание собственного стека. Применение рекурсии. "Чтобы понять рекурсию, сначала необходимо понять рекурсию".

Данное высказывание очень четко выражает суть рекурсии. Рекурсия является базовой концепцией программирования вообще, а не только JavaScript, понимание которой очень полезно. Она включает вызов функции из той же самой функции. Почему это может понадобиться? Предположим, что имеется массив массивов. Каждый из этих массивов может иметь в себе массивы, которые могут иметь массивы, которые могут иметь ... собственно, в этом и состоит идея. Таким образом мы имеем множество массивов в других массивах. Как выполнить одну и ту же операцию на всех элементах во всех этих массивах? Можно попробовать использовать простой цикл for, но неизвестно, сколько имеется массивов, и неизвестно, как глубоко распространяется вложение массивов. Поэтому остается только концепция рекурсии.

В этом примере мы циклически перебираем все элементы массива первого уровня. Если какой-либо из этих элементов в массиве сам будет массивом, мы снова вызываем функцию, передавая этот элемент как первичный массив. Затем функция будет перебирать этот массив и снова вызывать себя, пока не останется ни одного массива.

Другим хорошим примером рекурсии будет написание синтаксического анализатора документа XML. Каждый узел документа XML можно анализировать совершенно одинаково, поэтому мы можем разбить всю задачу на множество более мелких одинаковых шагов.

Самым трудным в рекурсии является ее понимание. Такие концепции, как циклы, воспринимаются достаточно естественно, в то время как рекурсия трудна для большинства людей. Рекурсивные функции также очень часто требуют больше памяти, чем нерекурсивные функции. Если имеется функция, которая вызывает себя на 20 уровней вглубь, потребуется как минимум в 20 раз больше памяти.

Простым примером будет написание рекурсивной функции факториала. Факториал N, записываемый как N!, определяется как произведение всех чисел от N до 1. Поэтому 5! будет равен 5*4*3*2*1 = 120.

function factorial(N){

return N<=1?1:N*factorial(N-1);

}

Демонстрационный пример. Факториал

Очень элегантное решение, не правда ли? В результате мы вызываем функцию факториала 5 раз для N = 5. Можно в действительности развернуть всю рекурсивную функцию и получить (5*(4*(3*(2*(1))))). Каждая пара скобок представляет новый вызов функции факториала. Можно также видеть, что если пользователь вводит число <=1, то всегда получит в качестве результата 1.

Давайте рассмотрим другой пример. При работе с программами рисования, такими, как Photoshop или MS Paint, иногда используется инструмент заливки (flood fill). Этот инструмент заливает выбранный цвет другим, указанным цветом. Это делается рекурсивно, и алгоритм заливки достаточно прямолинеен:

/*

это – псевдокод, быстро написанный и не функциональный,

который должен просто дать общую идею о том, как действует

реальный код

*/

function floodFill(x, y){

if(alreadyFilled(x, y)) return;

fill(x, y);

floodFill(x, y-1);

floodFill(x+1, y );

floodFill(x, y+1);

floodFill(x-1, y );

}

function fill(x, y){

// эта функция будет фактически изменять цвет поля

}

function alreadyFilled(x, y){

// эта функция проверяет, что поле уже было закрашено

}

Идея этого кода состоит в том, чтобы закрасить текущий квадрат или пиксель. Затем он пытается закрасить квадрат выше, справа, ниже и слева от себя. При таком алгоритме каждый квадрат будет закрашен достаточно быстро. Однако здесь возникает небольшая проблема – размер стека.

При вызове функции копия множества переменных, которые нужны ей для работы, сохраняется в памяти. Если функция вызывается рекурсивно, то другая копия всех этих переменных сохраняется в памяти, затем еще одна и т.д. Эти копии переменных сохраняются в так называемом стеке. Первая копия находится внизу, следующая поверх нее, и т.д. К сожалению, существует ограничение на размер стека. В большинстве браузеров этот предел определен где-то в районе 1000. Это означает, что для функции заливки сетка могла бы содержать до 1000 квадратов. Некоторые браузеры имеют меньший размер стека. Web-браузер Safari, например, имеет максимальный размер стека, равный примерно 100, поэтому даже небольшая сетка 10 х 10 исчерпает возможности браузера.

Таким образом мы имеем ограничение в самом браузере, которое определяет, что при использовании рекурсии можно углубиться только на 1000 уровней. К сожалению, наш алгоритм floodFill (заливки) будет в худшем случае углубляться на 1000 уровней на сетке, содержащей только 1000 полей. Если имеется что-то более сложное, то существует вероятность, что произойдет переполнение стека и просто остановка выполнения кода. Очевидно, что существуют ситуации, когда необходимо закрасить область, содержащую более 1000 пикселей. Что делать в таком случае? Попробуем изменить подход.

Прежде всего попробуем изменить алгоритм. Существует много различных алгоритмов закраски – мы использовали один из самых простых. Он проверяет все направления и затем закрашивает каждый просмотренный квадрат, если это будет необходимо. С помощью небольшого изменения можно существенно улучшить этот алгоритм, с точки зрения необходимого пространства стека. Вместо просмотра влево и вправо на 1 квадрат, можно просматривать влево и вправо на максимально возможное количество позиций и закрашивать каждый пиксель в этом направлении. Это называется алгоритмом закрашивания со сканированием по линиям, который оказывается одним из наиболее эффективных существующих алгоритмов закрашивания. К сожалению, он все еще имеет свои ограничения, и для достаточно большой области закрашивания он также может переполнять стек.

Если это произойдет, то остается единственный вариант: не использовать рекурсию. Вместо использования стека JavaScript можно создать свой собственный с помощью простого массива JavaScript. Так как массив не имеет ограничений на количество элементов массива, то можно получить "бесконечно" большой стек, которым мы управляем самостоятельно.

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

var Stack = [];

function floodFill(x, y){

fillPixel(x, y);

while(Stack.length>0){

toFill = Stack.pop();

fillPixel(toFill[0], toFill[1]);

}

}

function fillPixel(x, y){

if(!alreadyFilled(x, y)) fill(x, y);

if(!alreadyFilled(x, y-1)) Stack.push([x, y-1]);

if(!alreadyFilled(x+1, y )) Stack.push([x+1, y ]);

if(!alreadyFilled(x, y+1)) Stack.push([x, y+1]);

if(!alreadyFilled(x-1, y )) Stack.push([x-1, y ]);

}

function fill(x, y){

// эта функция будет фактически изменять цвет поля

}

function alreadyFilled(x, y){

// эта функция проверяет, что квадрат еще не был закрашен

}

Как можно видеть, процесс не намного сложнее, но требует немного больше микроуправления, чем написанный ранее рекурсивный код. Вместо рекурсивного вызова функции floodFill создается переменная Stack, содержащая список квадратов, которые необходимо закрасить. Затем функция fillPixel заполняет этот массив, а функция floodFill извлекает последний элемент и закрашивает его. Когда все будет сделано, результат будет таким же, как и у первой функции, которая была написана, с одним исключением: эта функция не имеет никаких ограничений в отношении величины сетки.

Отметим, что существует очень немного рекурсивных функций, которые будут реально переполнять стек JavaScript. В действительности это не совсем верно. Почти любая рекурсивная функция может переполнить стек, но чаще всего данные, которые функция получает от пользователя, делают это крайне маловероятным событием. Когда, например, вы встретите документ XML с глубиной вложения узлов, равной 1000? Почти наверняка – никогда.

Теперь, имея некоторое представление о рекурсии, надо попытаться понять, что с ней можно делать, кроме закрашивания изображений. Одним из наиболее распространенных рекурсивных алгоритмов будет так называемый двоичный поиск. Это можно представить себе как игру на больше-меньше. Если кто-то предлагает угадать число от 1 до 100, то, скорее всего, начать лучше с 50. Если партнер скажет, что больше, то можно предположить 75 и т.д. Это можно продолжать, пока число не будет найдено.

Как оказывается, это один из самых быстрых способов поиска данных, когда известно, что все данные уже отсортированы. Если имеется список из 1000000 позиций и требуется найти одну из них, то можно начать с 500000 и использовать тот же процесс, что и в игре "больше-меньше".

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

Другим широко распространенным использованием рекурсии является проверка или синтаксический анализ некоторых данных. Ранее в качестве примера упоминался файл XML, но с помощью рекурсии можно эффективно выполнять многие другие формы синтаксического анализа, такие, как подсчет количества вхождений слова или фразы в предложении или книге.

Рекурсия является крайне полезной концепцией. Рекурсия может использоваться не так часто, но когда она находит применение, она существенно облегчает жизнь программиста.