Рекурсия

От лат 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 страница B передает по ссылке странице A, пока мы не сосчитали, какой PageRank получила страница B от всех прочих страниц, которые на нее сослались, а этого нельзя узнать, пока мы не посчитаем PageRank этих страниц… продолжать? Наверное, уже не надо. Это опять Она — Её Величество Рекурсия¹⁾.

Яндексовский тИЦ устроен точно так же: A получает свою долю веса от B, чей вес точно так же нужно определить по весу ссылающихся на него… в общем, см. выше и не будем впадать в рекурсию повторяться. ТИЦ отличается от гугловского PageRank тем, что считается для сайтов в целом, а не для отдельных страниц. Поэтому Яндексу вроде бы живется полегче: сайтов все-таки на порядки меньше, чем страниц на них, так что пересчитать тИЦ — плевое дело в сравнении с пересчетом PageRank.

Однако тИЦ на выдачу не влияет. Для влияния на выдачу у Яндекса есть старательно спрятанный от оптимизаторских глаз ВИЦ, а это уже параметр страницы и аналог PageRank, так что считать Яндексу не пересчитать. Его счастье, что он пока обрабатывает только Россию и СНГ… да еще недавно в Турцию зачем-то полез. Но это же не вся планета — сколько там, в самом деле, той Турции…

В силу рекурсивного алгоритма расчета ссылочного веса вполне очевидно, что две страницы, взаимно (или через третью, «по кольцу») ссылающиеся друг на друга, в ходе расчета могут получать неоправданно высокий вес. Поэтому вскоре после публикации алгоритма PageRank оптимизаторы начали экспериментировать с рекурсивной линковкой — как отдельных страниц сайта, так и сайтов в целом. Эксперименты подтвердили эффективность рекурсивной перелинковки.

Поскольку поисковые системы (прежде всего Google) не смогли устранить эффект ссылочной рекурсии более цивилизованными средствами, ссылочные кольца стали не программно «размыкать», а попросту банить. Признак рекурсии так же очевиден, как и ее идея — уже со второй итерации расчета PR таких страниц растет лавинообразно (проверено на экспериментальной модели). По этому признаку несложно выявить кольцевые структуры. При этом — впрочем, как всегда — машина не может провести границу между намеренной накачкой PR и ссылочными замыканиями естественного (случайного) происхождения. Есть подозрение, что до сих пор ни в чем плохом не замешанные сайты влетают под санкции из-за рекурсивных ссылочных структур, образовавшихся непреднамеренно.

Возможно, такими экспериментами частично объясняется и распространенный SEO-миф о сайтах, получавших PR=3 на главной без внешних ссылок, только за счет большого числа страниц.

Возьмем более сложный пример случайной рекурсии. Как известно, ссылки с псевдосайтов в бирже sape раскупают лучше при наличии пузомерок - тИЦ и PR. Но, поскольку такие сайты большей частью однодневки, покупать на них ссылки на постоянной основе - нелепо, и проще их купить в той же sape. В свою очередь с этих сайтов покупают ссылки другие сайты, которые тоже торгуют на бирже, а на них покупают первые сайты… То есть образуются огромные группы сайтов, ссылающиеся друг на друга, чтобы продавать друг другу воздух. Некий ссылочный форекс. В выигрыше бывает тот, кто умнее выбрал стратегию продажи и закупки ссылок.

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