Главная › Услуги › Рекурсия и рекурсивные алгоритмы

Рекурсия и рекурсивные алгоритмы

Что такое рекурсия?

Под этим словом подразумевается процесс, обозначающий повторение одних и тех же элементов «самоподобным образом». Достойный пример такого процесса — русская матрешка, и если бы не предел возможностей, то такая бы игрушка повторяла себя до бесконечности.

Исходя из технических причин, рекурсия все-таки величина конечная.

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

Примером математической рекурсии может служить уже всем изрядно надоевший пример — вычисление факториала. В действительности рекурсия в веб-программировании применяется довольно таки часто, а все потому, что рекурсия – это единственный вариант обхода любой стандартной структуры, когда точно не знают о ее реальных размерах и глубине вложения. Без нее также не обходится и построение графов. Это классический вариант.

Чтобы убедиться в необходимости этого процесса, стоит попробовать построить карту сайта с разделами по иерархической структуре вложенных списков. Это будет нереально, если вы не ограничитесь заранее ее размерами и глубиной вложения. Но если, все-таки вы соорудите нечто подобное, то поймете, что в какой-то момент вся ваша конструкция зависнет и перестанет работать.

Рекурсия в поисковых системах

Поисковые системы также зависят от рекурсии. Именно с того момента, когда был введен критерий авторитетности сайтов измерять количеством ссылок, поисковые системы также попались в эти сети. Ссылочная «масса» сайта складывается из мелких кусочков «масс» всех тех ресурсов, которые на него ссылаются. Чтобы высчитать этот показатель для одного сайта, необходимо просчитать «массу» всех ссылочных вариантов, которые в свою очередь состоят из других таких же компонентов, и так далее, по всей глубине поисковой сети. Вот вам и рекурсия на практике.

Рекурсивный PageRank oт Google

Такое имя носит алгоритм расчета, созданный и опубликованный Google. Этот алгоритм известен уже давно, но сколько бы раз он не преобразовывался и не дополнялся всевозможными усовершенствованиями, в основе лежит все тот же рекурсивный метод. Суть всегда остается одна и та же: расчеты, перерасчеты и еще раз перерасчеты. В результате получается опять та же функция.

Рекурсивный тИЦ от Яндекса

ТИЦ, созданный Яндексом, имеет точно такое же устройство, как и предыдущий алгоритм. Отличие заключается лишь в том, что он считается для всего сайта в целом, а не для каждой отдельной страницы. Именно поэтому поисковой системе Яндекс живется гораздо вольготнее, чем остальным, так как самих сайтов в разы меньше, чем страниц и пересчитать их намного легче.

Однако этот показатель на выдачу в Яндексе не влияет. Для этих целей у него есть глубоко спрятанный ВИЦ, который является аналогом PageRank. Так что объем подсчетов у Яндекс также немалый.

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

Прокомментировать эту статью:

Пожалуйста, зарегистрируйтесь для комментирования.

Рекурсивный алгоритм

Реку́рсия - метод определения класса объектов или методов предварительным заданием одного или нескольких (обычно простых) его базовых случаев или методов, а затем заданием на их основе правила построения определяемого класса, ссылающегося прямо или косвенно на эти базовые случаи.

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

Примеры

Алгоритм по передвижению башни, алгоритм передвинет нужное количество дисков из пирамиды «источник» на пирамиду «задание» используя «запасную» пирамиду.

Если число дисков равно одному, тогда:

Передвиньте диск из источника в задание

В противном случае:

Рекурсивно передвиньте все диски кроме одного из источника в запас, используя задание как запас
Передвиньте оставшийся диск из источника в задание
Передвиньте все диски из запаса в задание используя источник как запас

Рекурсия в программировании

Функции

Class element_of_list { element_of_list *next; /* ссылка на следующий элемент того же типа */ int data; /* некие данные */ } ;

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

Рекурсия в физике

Классическим примером бесконечной рекурсии являются два поставленные друг напротив друга зеркала : в них образуются два коридора из затухающих отражений зеркал.

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

Рекурсия в лингвистике

Способность языка порождать вложенные предложения и конструкции. Базовое предложение кошка съела мышь может быть за счет рекурсии расширено как Ваня догадался, что кошка съела мышь , далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий , то есть свойственна любому естественному языку (хотя в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии - пираха, которое отмечает лингвист Д. Эверетт). О рекурсии в лингвистике, ее разновидностях и наиболее характерных проявлениях в русском языке описано в статье Е.А.Лодатко "Рекурсивные лингвистические структуры" (см.: Рекурсивные лингвистические структуры)

Цитаты

Юмор

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

Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:

Рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого », в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки».
Рассказ о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).

Русская народная сказка-песня «У попа была собака…» являет пример рекурсии:

У попа была собака, он её любил,
Она съела кусок мяса, он её убил,
В землю закопал,
Надпись написал:
"У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: "У попа была собака, он её любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись написал: …

См. также

Рекуррентная последовательность (возвратная последовательность)

Ссылки

Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. - 2-е изд. - М.: «Вильямс» , 2006. - С. 1296. - ISBN 0-07-013151-1

Wikimedia Foundation . 2010 .

Смотреть что такое "Рекурсивный алгоритм" в других словарях:

рекурсивный алгоритм - rekursyvusis algoritmas statusas T sritis automatika atitikmenys: angl. recursive algorithm vok. rekursiver Algorithmus, m rus. рекурсивный алгоритм, m pranc. algorithme récursif, m … Automatikos terminų žodynas

рекурсивный алгоритм управления - rekursyvusis valdymo algoritmas statusas T sritis automatika atitikmenys: angl. recursive control algorithm vok. rekursiver Regelungs od. Steuerungs algorithmus, m rus. рекурсивный алгоритм управления, m pranc. algorithme de réglage récurrent, m … Automatikos terminų žodynas

Это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях… … Википедия

Рекурсивный акроним акроним (иногда бэкроним), который ссылается на себя. В среде компьютерных хакеров стало традиционным выбирать акронимы и аббревиатуры, которые косвенно или напрямую ссылаются на себя. Одним из самых ранних примеров… … Википедия

- (англ. Recursive descent parser) алгоритм синтаксического анализа, реализуемый путём взаимного вызова парсящих процедур, соответствующих правилам контекстно свободной грамматики или БНФ. Применения правил последовательно, слева направо … Википедия

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

У этого термина существуют и другие значения, см. Алгоритм (значения). Для улучшения этой статьи желательно?: Переработать оформление в соответствии с правил … Википедия

Алгоритмы поиска на графах A* B* Алгоритм Беллмана Форда Двунаправленный поиск Алгоритм Дейкстры Алгоритм Джонсона Поиск в ширину Поиск в глубину Поиск с ограничением глубины Поиск по первому наилучшему совпадению Алгоритм Флойда Уоршелла Поиск… … Википедия

У этого термина существуют и другие значения, см. Ppm. PPM (англ. Prediction by Partial Matching предсказание по частичному совпадению) адаптивный статистический алгоритм сжатия данных без потерь, основанный на контекстном… … Википедия

Функций: рекурсивно заданная функция в своём определении содержит себя, в частности, рекурсивной является функция, заданная рекуррентной формулой . Таким образом, можно одним выражением дать бесконечный набор способов вычисления функции, определить множество объектов через самого себя с использованием ранее заданных частных определений.

Данные

Struct element_of_list { element_of_list * next; /* ссылка на следующий элемент того же типа */ int data; /* некие данные */ } ;

Рекурсивная структура данных зачастую обуславливает применение рекурсии для обработки этих данных.

В физике

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

В лингвистике

Способность языка порождать вложенные предложения и конструкции. Базовое предложение «кошка съела мышь » может быть за счёт рекурсии расширено как Ваня догадался, что кошка съела мышь , далее как Катя знает, что Ваня догадался, что кошка съела мышь и так далее. Рекурсия считается одной из лингвистических универсалий , то есть свойственна любому естественному языку. Однако, в последнее время активно обсуждается возможное отсутствие рекурсии в одном из языков Амазонии - пираха, которое отмечает лингвист Дэниэл Эверетт (англ. ) .

В культуре

Большая часть шуток о рекурсии касается бесконечной рекурсии, в которой нет условия выхода, например, известно высказывание: «чтобы понять рекурсию, нужно сначала понять рекурсию» .

Весьма популярна шутка о рекурсии, напоминающая словарную статью:

Несколько рассказов Станислава Лема посвящены (возможным) казусам при бесконечной рекурсии:

рассказ про Йона Тихого «Путешествие четырнадцатое» из «Звёздных дневников Ийона Тихого », в котором герой последовательно переходит от статьи о сепульках к статье о сепуляции, оттуда к статье о сепулькариях, в которой снова стоит отсылка к статье «сепульки»:

Нашёл следующие краткие сведения:
«СЕПУЛЬКИ - важный элемент цивилизации ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКАРИИ».
Я последовал этому совету и прочёл:
«СЕПУЛЬКАРИИ - устройства для сепуления (см.)».
Я поискал «Сепуление»; там значилось:
«СЕПУЛЕНИЕ - занятие ардритов (см.) с планеты Энтеропия (см.). См. СЕПУЛЬКИ».

Лем С. «Звёздные дневники Ийона Тихого. Путешествие четырнадцатое.»

Рассказ из «Кибериады» о разумной машине, которая обладала достаточным умом и ленью, чтобы для решения поставленной задачи построить себе подобную, и поручить решение ей (итогом стала бесконечная рекурсия, когда каждая новая машина строила себе подобную и передавала задание ей).
Рекурсивные акронимы : GNU (GNU Not Unix), PHP (PHP: Hypertext Preprocessor) и т. д.

См. также

Возвратная последовательность

Примечания

Wikimedia Foundation . 2010 .

Смотреть что такое "Рекурсия" в других словарях:

Возвращение, повторение Словарь русских синонимов. рекурсия сущ., кол во синонимов: 1 … Словарь синонимов

рекурсия - — [] рекурсия В общем смысле вычисление функции по определенному алгоритму. Примерами таких алгоритмов являются рекуррентные формулы, выводящие вычисление заданного члена… … Справочник технического переводчика

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

Рекурсия - Терапевтический паттерн, когда берётся некоторое условие или критерий, сформулированный в исходном утверждении, и применяется к самому утверждению. Например: У меня нет времени. Сколько времени вам пришлось потратить, чтобы убедиться, что у вас… … Большая психологическая энциклопедия

Способ определения функций, являющийся объектом изучения в теории алгоритмов и других разделах математич. логики. Этот способ давно применяется в арифметике для определения числовых последовательностей (прогрессии, чисел Фибоначчи и пр.).… … Математическая энциклопедия

рекурсия - (фон.) (лат. recursio возвращение). Одна из трех фаз артикуляции звуков, отступ. Перевод органов речи в спокойное состояние или приступ к артикуляции следующего звука. В слове отдых рекурсия (отступ) при артикулировании [т] может наложиться на… … Словарь лингвистических терминов Т.В. Жеребило

От лат recursio (возвращение). В общем случае так называется процесс повторения элементов «самоподобным образом».

Яркий пример рекурсии - матрёшки. Рекурсивное определение: «матрёшка - это разъемная пустотелая деревянная кукла, содержащая внутри матрёшку меньшего размера». Вот такая рекурсия по-русски. И если бы не предел возможностей мастеров, идеальная матрёшка уходила бы в глубь себя до атомарного уровня. А то и глубже. Просто у Левши не нашлось мелкоскопа достаточной силы. Верхний предел теоретически тоже не ограничен, но баобабы подходящего размера на нашей планете не растут. В общем, по техническим причинам рекурсия должна быть конечной.

В программировании (как и в математике) рекурсия - процесс вызова функцией самой себя (прямая рекурсия), либо вызов изнутри функции A функции B, которая в свою очередь содержит вызов функции A (косвенная или взаимная рекурсия). Разумеется, рекурсивные вызовы должны иметь выполнимое условие завершения, иначе такая программа «зависнет», как в бесконечном цикле - но, в отличие от бесконечного цикла, при бесконечной рекурсии она аварийно завершится переполнением стека.

Пример рекурсии

Самый надоевший пример рекурсии в математическом программировании - вычисление факториала. Не будем изменять славным традициям. Для тех, кто еще не проходил: N! (факториал N) - это произведение всех натуральных чисел от единицы до N (факториал нуля равен 1).
Можно тупо перемножать числа от 1 до N в цикле. А можно соорудить функцию factorial(n), которая будет содержать условие и вызов самой себя. Если n равно единице, то функция возвращает значение 1, иначе возвращает значение n, умноженное на factorial(n-1).
Зарисовка на PHP

Function factorial($n) { if ($n == 1) { return 1; } else { return intval($n * factorial($n - 1)); } }

Практические применения рекурсии

«Ну, и зачем это здесь нужно?» - спросит нас нетерпеливый юный читатель - «Чушь научная, занудство, факториалы всякие… А практически к чему эту рекурсию приложить?»
«К подбитому глазу веб-программированию» - без колебаний ответим мы. И тут же это обоснуем.

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

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

Рекурсия в поисковых системах

Да, именно так. Поисковым системам от рекурсии тоже некуда деваться. С тех пор, как был заведен обычай мерить авторитетность сайта (документа) количеством ссылок, поисковики попались в рекурсивную ловушку, и пусть они блуждают в ней вечно (это искреннее доброе пожелание автора). Ссылочный «вес» сайта складывается из маленьких кусочков «веса» от всех тех, которые на него ссылаются. Чтобы вычислить этот вес для A, на которого ссылаются B, C и D, надо обсчитать их вес, который в свою очередь передается всякими другими, вес которых тоже нужно обсчитывать… и так по всей учтенной в поисковике Сети. Совершенно рекурсивная задачка. А вы говорите - сплошная теория. Самая что ни на есть реальная практика.

Рекурсивный PageRank от Google

Свой базовый алгоритм расчета PageRank создатели Google опубликовали давно. И как бы он с тех пор ни менялся, сколько бы его ни дополняли усовершенствованиями, основа остается прежней. Нельзя узнать, какую величину PageRank страница B передает по ссылке странице A, пока мы не сосчитали, какой PageRank получила страница B от всех прочих страниц, которые на нее сослались, а этого нельзя узнать, пока мы не посчитаем PageRank этих страниц… продолжать? Наверное, уже не надо. Это опять Она - Её Величество Рекурсия .

Энциклопедичный YouTube

1 / 5
В математике рекурсия имеет отношение к методу определения функций и числовых рядов: рекурсивно заданная функция определяет своё значение через обращение к себе самой с другими аргументами. При этом возможно два варианта:
e = 2 + 2 2 + 3 3 + 4 4 + … = 2 + f (2) {\displaystyle e=2+{\cfrac {2}{2+{\cfrac {3}{3+{\cfrac {4}{4+\ldots }}}}}}\;=2+f(2)} , где f (n) = n n + f (n + 1) {\displaystyle f(n)={\cfrac {n}{n+f(n+1)}}} Прямой расчёт по приведённой формуле вызовет бесконечную рекурсию, но можно доказать, что значение f(n) при возрастании n стремится к единице (поэтому, несмотря на бесконечность ряда, значение числа Эйлера конечно). Для приближённого вычисления значения e достаточно искусственно ограничить глубину рекурсии некоторым наперёд заданным числом и по достижении его использовать вместо f (n) {\displaystyle f(n)} единицу.
Другим примером рекурсии в математике является числовой ряд, заданный рекуррентной формулой , когда каждый следующий член ряда вычисляется как результат функции от n предыдущих членов. Таким образом с помощью конечного выражения (представляющего собой совокупность реккурентной формулы и набора значений для первых n членов ряда) может даваться определение бесконечного ряда.

Struct element_of_list { element_of_list * next ; /* указатель на следующий элемент того же типа */ int data ; /* некие данные */ };

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