В этой статье расскажу вам о рекурсии и о том как грамотно работать с ней на языке PHP.
PHP расшифровывается как PHP: Hypertext Preprocessor. Это смущает многих людей, потому что первое слово аббревиатуры это аббревиатура. Этот тип аббревиатуры называется рекурсивной аббревиатурой.
Перевод Google из официальной документации по 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 мы будем иметь отставание рекурсивной версии от его итеративного эквивалента, которое может быть значительным в практическом плане. Тогда же в чём смысл рекурсии спросите вы?
Предлагаю вам пока самостоятельно поразмышлять на эту тему.
Есть материалы отсюда.