Рекурсия и стек

Всем доброго дня. В качестве небольшого предисловия к следующей работе по поиску данных, хотим сказать пару слов о таком интересном понятии как РЕКУРСИЯ. Оно знакомо тем, кто хоть немного разбирается в программировании. Для всех остальных краткий ликбез)

ИТАК, РЕКУРСИЯ ПРОСТЫМИ СЛОВАМИ...

Аналогичный запрос к Google выдал нам определение…

Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).

Фильтруем много слов и выделяем главное – функция вызывает саму себя.

Для чего можно использовать такой прием? В первую очередь для упрощения понимания кода. Сложная задача разбивается на несколько аналогичных, но более простых или упрощается до несложных действий в дополнение к такому простому варианту.

Для продолжения разговора обозначим терминологию:

Глубина рекурсии – общее количество вложенных вызовов (включая первый).

База рекурсии – элементарная задача (аргумент), для нее решение определено.

Шаг рекурсии – способ сведения задачи к более простым. Каждый шаг рекурсии – это шаг к ее базе.

Надо иметь в виду, что рекурсивный код может быть заменен на более сложный и менее понятный итеративный. Такой вариант реализуется, если требуется оптимизировать выполнение задачи.

Для того чтобы понять как работают такие рекурсивные функции введём еще одно понятие.

Контекст выполнения – специальная внутренняя структура данных, которая содержит информацию о вызове функции. Она включает в себя конкретное место в коде, на котором находится интерпретатор, локальные переменные функции, значение this и прочую служебную информацию. Одному вызову функции соответствует один контекст выполнения.

Итак, что происходит когда функция производит вложенный вызов:

Выполнение текущей функции приостанавливается.

Контекст выполнения, связанный с ней, запоминается в специальной структуре данных – стеке контекстов выполнения.

Выполняются вложенные вызовы, для каждого из которых создаётся свой контекст выполнения.

После их завершения старый контекст достаётся из стека, и выполнение внешней функции возобновляется с того места, где она была остановлена.

В изображениях к посту приведен небольшой пример в виде: формулировки задачи, алгоритма, описания и программной реализации

При написании этого поста мы использовали материалы статьи на сайте Современного учебника по JavaScript по ссылке ниже

Источник: learn.javascript.ru

Комментарии: