Рекурсия на PHP

В этой статье расскажу вам о рекурсии и о том как грамотно работать с ней на языке PHP.

PHP расшифровывается как PHP: Hypertext Preprocessor. Это смущает многих людей, потому что первое слово аббревиатуры это аббревиатура. Этот тип аббревиатуры называется рекурсивной аббревиатурой.

Перевод Google из официальной документации по PHP

Содержание

• Понятие рекурсии
• Глубина рекурсии
• Опасности и подводные камни рекурсии
• Рекурсивные алгоритмы на PHP
  • Вычисление последовательности Фибоначчи

Понятие рекурсии

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

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

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

Другим примером можно взять всем хорошо известное детское стихотворение:

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

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

…
Эта докучная сказка представляет собой пример простой рекурсии (здесь функция вызывает саму себя).

Глубина рекурсии

В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.

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

Для нас важно, что ограничениям подвержен и сам компьютер. Память компьютера, производительность — не бесконечны. Поэтому применяя рекурсию, нужно понимать её опасности и подводные камни.

Опасности и подводные камни рекурсии

Рассмотрим простой пример.

<?php

// Пример бесконечной рекурсии

function foo(){
  return foo();
}

foo();

?>

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

То же самое касается и примера со сложной рекурсией.

<?php

// Пример сложной бесконечной рекурсии

function foo(){
  return bar();
}

function bar(){
  return foo();
}

foo();

?>

В PHP две функции не могут вызывать друг друга бесконечно, так как это неизбежно
приведёт к падению программы.

Теперь вернёмся к понятию глубины рекурсии. И рассмотрим следующий пример.

<?php

// Пример конечной рекурсии

function foo($n){
  if($n < 1)
    return;
  return foo($n-1);
}

foo(100000);

?>

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

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

Теперь мы можем приступить к исследованию алгоритмов основанных на рекурсии.

Существует множество таких алгоритмов:

• Нахождение факториала
• Вычисление последовательности Фибоначчи
• Поиск максимального элемента в массиве
• Вычисление перестановок Ханойских башен
• Рассчёт вариантов размена суммы монетами
• Рекурсивный обход дерева
• и т.д.

Рассмотрим некоторые из них.

Вычисление последовательности Фибоначчи

Следует сделать лирическое отступление, которое касается истории открытия данной последовательности…

В 1202 году Леонардо Пизанский, известный как Фибоначчи, решая задачу о размножении кроликов, пришёл к открытию рекуррентного соотношения:
Эта последовательность обладает одним замечательным свойством, а именно:
Число Фи, представляет собой золотую пропорцию, которая часто встречается в природе, выражая собой закон гармонии и красоты…

Вернёмся к нашему алгоритму. Знание рекуррентного соотношения позволяет нам с лёгкостью реализовать этот алгоритм на PHP:

<?php

// Рекурсивный алгоритм вычисления последовательности Фибоначи

function F($n){
	if($n<=1){
		return 1;
	}
	return F($n-1)+F($n-2);
}

?>

С точки зрения программирования нам интересно знать насколько быстро он выполняется по сравнению с его реализацией на основе итераций, например этой:

<?php

// Итеративный алгоритм вычисления последовательности Фибоначчи

function F($n){
  $i=1; $r=1; $l=1; $s=1;
  while($i++<$n){
    $s=$l+$r;
    $l=$r;
    $r=$s;
  }
  return $s;
}

?>

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

Дело в том, что реализация рекурсивного алгоритма “в лоб” обладает одним существенным недостатком. А именно при такой реализации вызов функции для одного и того же аргумента производится многократно. Чтобы это увидеть, нужно внимательно рассмотреть само рекуррентное соотношение.

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

<?php

// Рекурсивный алгоритм Фибоначчи
// с использованием подхода восходящего динамического программирования

function F_recursive($n, $K){
	if($n<=1) {
		return 1;
	} elseif ($K[$n] == 0) {
		$K[$n]=F_recursive($n-1,$K) + F_recursive($n-2,$K);
	}
	return $K[$n];
}

function F($n){
	$K=array_fill(0,$n+1,0);
	return F_recursive($n,$K);
}

?>

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

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

<?php

// Рекурсивный алгоритм Фибоначчи
// с применением Объектно-Ориентированного Подхода

class Fibonachi {
  private $K;

  private function F_recursive($n){
  if($n<=1) {
  	return 1;
  } elseif ($this->K[$n] == 0) {
  	$this->K[$n]=$this->F_recursive($n-1,$this->K) + $this->F_recursive($n-2,$this->K);
  }
  return $this->K[$n];
  }

  // Интерфейс класса
  public function getNumberByIndex($n){
    $this->K=array_fill(0,$n+1,0);
    return $this->F_recursive($n);
  }
}

function F($n){
  $Fibonachi = new Fibonachi();
  return $Fibonachi->getNumberByIndex($n);
}

?>

Время выполнения этой программы уже приближается к времени выполнения программы основанной на итерациях. Но всё же для достаточно больших значений n мы будем иметь отставание рекурсивной версии от его итеративного эквивалента, которое может быть значительным в практическом плане. Тогда же в чём смысл рекурсии спросите вы?

Предлагаю вам пока самостоятельно поразмышлять на эту тему.

Есть материалы отсюда.