}
}
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, но с помощью рекурсии можно эффективно выполнять многие другие формы синтаксического анализа, такие, как подсчет количества вхождений слова или фразы в предложении или книге.
Рекурсия является крайне полезной концепцией. Рекурсия может использоваться не так часто, но когда она находит применение, она существенно облегчает жизнь программиста.
Дополнения
Дополнение. Краткое руководство по AJAX
Технология AJAX является не новым языком программирования, а просто новым способом использования существующих стандартов.
С помощью AJAX можно создавать Web-приложения, которые будут лучше, быстрее и удобнее для пользователей, чем существующие.
AJAX основывается на JavaScript и запросах HTTP.
AJAX является сокращением от "Asynchronous JavaScript And XML" (Асинхронный JavaScript и XML).
AJAX является не новым языком программирования, а просто новым способом создания Web-приложений, которые будут лучше, быстрее, и более интерактивными.
AJAX использует JavaScript для отправки и получения данных при взаимодействии Web-браузера и Web-сервера.
Технология AJAX делает Web-страницы более гибкими и быстро реагирующими, осуществляя обмен данными с Web-сервером в фоновом режиме, а не перезагружая всю Web-страницу всякий раз, когда пользователь делает изменение.
AJAX является технологией, которая выполняется в браузере клиента. Она использует асинхронную передачу данных (запросы HTTP) между браузером и Web-сервером, позволяя Web-страницам запрашивать с сервера небольшие объемы данных вместо целых страниц.
Эта технология позволяет уменьшить объем приложений Интернет, сделать их более быстрыми и более удобными для пользователей.
AJAX является технологией Web-браузера, которая не зависит от программного обеспечения Web-сервера.
AJAX использует следующие открытые стандарты:
JavaScript
XML
HTML
CSS
Используемые в AJAX открытые стандарты строго определены и поддерживаются всеми основными браузерами. Приложения AJAX не зависят от используемых браузеров и платформ.
Web-приложения имеют множество преимуществ при сравнении с традиционными приложениями настольных компьютеров. Они имеют более обширную аудиторию, их легче устанавливать и поддерживать, и их легче разрабатывать.
Однако приложения Интернет не всегда бывают достаточно "богаты" свойствами и удобны для использования по сравнению с традиционными приложениями.
С помощью AJAX приложения Интернет можно сделать богаче (меньше, быстрее, и легче в использовании).
Нет ничего нового, что требует изучения.
Технология AJAX основывается на открытых стандартах. Эти стандарты использовались множеством разработчиков многие годы.
Большинство существующих Web-приложений можно легко переписать с помощью технологии AJAX вместо традиционных форм HTML.
Традиционное Web-приложение посылает введенные данные на Web-сервер (используя форму HTML). После обработки данных Web-сервер возвращает пользователю совершенно новую Web-страницу.
Так как сервер возвращает новую Web-страницу всякий раз, когда пользователь посылает данные на сервер, то традиционное Web-приложение часто выполняется медленно и оказывается менее удобным для пользователя.
С помощью AJAX Web-приложения могут посылать и получать данные без перезагрузки всей Web-страницы. Это делается с помощью запросов HTTP, посылаемых на сервер (в фоновом режиме), и модификации только отдельных частей Web-страницы с помощью JavaScript, когда сервер возвращает данные.
XML используется обычно в качестве формата для получения данных сервера, хотя можно использовать любой формат, включая обычный текст.
Как это делается, будет показано далее в этом кратком руководстве.
Технологию AJAX можно использовать для создания приложений с большими интерактивными возможностями.
В следующем примере приложения AJAX показано, как Web-страница может оперативно общаться с Web-сервером, когда пользователь вводит данные в Web-форму.
На странице выводится поле ввода с предложением ввести имя. Когда пользователь начинает вводить в этом поле имя, ниже появляются возможные варианты имен.
Пусть на Web-странице имеется форма HTML со следующим кодом:
<form>
Имя:
<input type="text" id="txt1"
onkeyup="showHint(this.value)">
</form>
<p>Советуем: <span id="txtHint"></span></p>
Как можно видеть, это простая форма HTML с полем ввода с именем "txt1".