Главная » Полезные статьи » Язык JavaScript » Javascript и рекурсия
Распечатать статью

Javascript и рекурсия

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

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

Данная концепция может быть трудна для понимания, но выделение времени для того, чтобы научиться писать рекурсивный код, приносит много пользы. Быстродействие методов сортировки может быть значительно увеличено с помощью рекурсии. Пример этого паттерн быстрой сортировки Хоара, разработанный в 60-ые годы. Правильно реализованный метод с использование рекурсии короче и требует меньше ресурсов. Другое преимущество – лучшие методы комбинаторного поиска. А многие методы математической индукции работают быстрее и проще реализуются с помощью рекурсии, например, вычисление факториала.

 

Прямой вызов рекурсии в Javascript

Существует два метода кодирования рекурсивных функций в Javascript: непосредственный вызов функции из самой себя и второй, используя косвенный вызов.

Вот пример прямого вызова функции:

function recursMe(param) {
     if (param < 0) {     //base case
         return -1;
      }
     else {
          //some code here
          recursMe(param);
      }
}

Позволяя функции вызывать саму себя, можно нарваться на распространенную ошибку – бесконечные циклы. При написании рекурсивных функций нужно тщательно планировать базовый случай (прим. аргументы, для которых значения функции определены), чтобы избежать бесконечного цикла. Базовый случай – это условие завершения или «стопор» для цикла. В примере выше базовый случай if(param<0). До тех порка условие истинно, рекурсия продолжается.

Если базовое условие никогда не истинно, функция зависает в бесконечно цикле и программа не закончится, пока не будет исчерпана вся память и не произойдет сбой. Один из способов избежать бесконечного цикла, встраивание точек останова или условия выхода. Например, если функция запускается 10 раз, то автоматически выйти.

Косвенный вызов в JavaScript

Теперь взглянем на вызов рекурсивной функции javascript косвенно:

function recursMe(param) {
     if (param < 0) {   //base case
          return -1;
     }
     else {
          //some code here
          setTimeout(“recursMe(“ + param + “)”, 1);
     }
}

Вызов следующей рекурсии использует функцию setTimeout(), страница не будет блокироваться, пока идет расчет рекурсивной функции. Пользователь сможет скроллировать страницы, и другие процессы могут выполняться.

Синтаксис setTimeout:

timeoutId = setTimeout([скрипт для запуска], [время в миллисекундах]);

setTimeout() возращает идентификатор или дескриптор таймера, которые был запущен, который позже может быть использован для отмены выполнения функции, используя функцию clearTimout (timeoutId), если необходимо.

Вызов рекурсивных функций косвенно также уменьшает вероятность ошибки переполнения стека. Эти ошибка происходит, когда рекурсия израсходует стек, выделенный браузером. Размер стека в различных браузерах, выделенный их javascript движку, сильно различается, от примерно 500 у браузера Safari до более 21000 у Chrome. Каждый раз, когда ваша рекурсивная функция вызывается напрямую, копия всех переменных функции добавляются в стек. Когда функция завершает работу, переменные удаляются из стека.

В Safari, если стек размер стека достигает 501, пользователь получит ошибку переполнения стека, и страница не будет работать правильно.

Вывод

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

Удачного кодирования!

Источник:  css-live.ru
Вы можете оставить комментарий, или обратную ссылку на Ваш сайт.

Оставить комментарий

Похожие статьи