В одной из моих предыдущих статей я писал об итераторах и о том, как их использовать. Сегодня я хотел бы взглянуть на братского близнеца итерации: рекурсии.
Прежде чем говорить о рекурсии, давайте взглянем на этот фрагмент кода:
<?php function factorial($number) { if ($number < 0) { throw new InvalidArgumentException('Number cannot be less than zero'); } $factorial = 1; while ($number > 0) { $factorial *= $number; $number --; } return $factorial; } Факториал — это результат числа, умноженного на все натуральные числа, меньшие этого числа, и функция выше вычисляет факториал любого числа, данного ему, используя простой цикл. Теперь давайте перепишем пример следующим образом:
<?php function factorial_recursive($number) { if ($number < 0) { throw new InvalidArgumentException('Number cannot be less than zero'); } if ($number == 0) { return 1; } return $number * factorial_recursive($number – 1); }
Мы получаем одинаковые результаты при вызове обеих функций, но заметим, что вторая функция вычисляет факториал, вызывая себя. Это известно как рекурсия.
Что такое рекурсия?
Рекурсивная функция — это та, которая вызывает себя напрямую или в цикле вызовов функций.
Рекурсия также может относиться к методу решения проблем, который сначала решает меньшую версию проблемы, а затем использует этот результат плюс некоторые другие вычисления для формулирования ответа на исходную проблему. Часто в процессе решения меньшей версии метод решает еще меньшую версию проблемы и т. Д., Пока не достигнет «базового варианта», который тривиально решить.
Чтобы написать рекурсивную функцию, вам нужно предоставить ей какие-то средства возврата, иначе она будет вызывать себя вечно (или пока стек вызовов не взорвется, сценарий не истечет, или память не будет исчерпана). Это известно как пункт охраны или базовый случай.
Простейшая форма рекурсивной функции выглядит следующим образом:
<?php function my_recursive_func (args) { if (simplest case) { // The Base Case/Guard Clause that stops the // function from running forever return simple value; } else { //call function again with simpler args my_recursive_func(argsSimplified); } }
Типы рекурсии
Когда функция вызывает себя напрямую, это называется прямой рекурсией. Функция в цикле вызовов функций, которая в конечном итоге вызывает себя, называется косвенной рекурсией. Посмотрите на пример ниже косвенной рекурсии:
<?php function A($num) { $num -= 1; if($num > 0) { echo "A is Calling B($num)n"; $num = B($num); } return $num; } function B($num) { $num -= 2; if($num > 0) { echo "B is Calling A($num)n"; $num = A($num); } return $num; } $num = 4; echo "Calling A($num)n"; echo 'Result: ' . A($num);
Вызов A (4) А звонит Б (3) B зовет A (1) Результат: 0
Приведенный выше пример — действительно бесполезный код, предназначенный для демонстрации того, как функция может вызывать себя косвенно через другую функцию. Вызов A(n>4) или B(n>4) приводит к тому, что вызываемая функция вызывается из другой функции.
Важно знать, что функция может вызывать себя косвенно, как это, но в этой статье мы будем иметь дело только с прямой рекурсией.
Практический пример
Чтобы показать, насколько мощной может быть рекурсия, мы напишем функцию, которая ищет ключ в массиве и возвращает результат.
<?php function find_in_arr($key, $arr) { foreach ($arr as $k => $v) { if ($k == $key) { return $v; } if (is_array($v)) { foreach ($v as $_k => $_v) { if ($_k == $key) { return $_v; } } } } return false; } $arr = [ 'name' => 'Php Master', 'subject' => 'Php', 'type' => 'Articles', 'items' => [ 'one' => 'Iteration', 'two' => 'Recursion', 'methods' => [ 'factorial' => 'Recursion', 'fibonacci' => 'Recursion', ], ], 'parent' => 'Sitepoint', ]; var_dump( find_in_arr('two', $arr), find_in_arr('parent', $arr), find_in_arr('fibonacci', $arr) );
строка 'Рекурсия' (длина = 9) строка 'Sitepoint' (длина = 9) логическое значение false
Все хорошо, но обратите внимание, что мы перебираем только два уровня глубоко в массиве, и поэтому поиск «Фибоначчи» на третьем уровне не удался. Если мы хотим найти массив неопределенной глубины, этого будет недостаточно. Вместо этого мы можем переписать поиск как рекурсивную функцию:
<?php function find_in_arr($key, $arr) { foreach ($arr as $k => $v) { if ($k == $key) { return $v; } if (is_array($v)) { $result = find_in_arr($key, $v); if ($result != false) { return $result; } } } return false; }
С помощью рекурсивной функции мы можем искать массив глубиной в несколько уровней, так как мы не жестко закодировали, насколько глубока функция. Он просто продолжает работать, пока не пройдет все значения в массиве.
Голова и Хвост Рекурсия
До сих пор во всех примерах мы использовали так называемую рекурсию головы. Когда функция вызывает себя, она ждет результата от вызова, прежде чем вернуть собственное значение. Можно написать функции таким образом, чтобы они не работали с возвращаемыми значениями, а вместо этого передали все необходимые значения в качестве параметров. Это известно как хвостовой вызов (или хвостовая рекурсия). Этот метод обычно предпочтительнее, так как время выполнения языка может иногда оптимизировать вызовы, так что нет опасности взорвать стек вызовов, но PHP этого не делает.
Ниже приведен наш факторный пример, модифицированный для выполнения хвостового вызова. Обратите внимание, что результат рекурсивного вызова возвращается, а не обрабатывается дальше.
<?php function factorial ($number, $factorial = 1) { if ($number < 0) { throw new InvalidArgumentException('Number cannot be less than zero (0)'); } if ($number == 0) { return $factorial; } else { return factorial($number - 1, $factorial * $number); } }
Генеральный Совет
Любой код, который может быть написан итеративно, также может быть написан рекурсивно. Однако это не всегда легко сделать (или даже разумно сделать). Рекурсия сияет при обходе деревьев и списков или при выполнении большинства O (n log n) сортировок. Когда вам нужно разделить повторяющуюся проблему, рекурсия подойдет лучше, чем итеративный подход, как в случае поиска в файловой системе, и вам необходимо ввести любые подкаталоги для поиска внутри. Там, где есть обход неопределенной глубины, рекурсия прекрасно работает.
Имейте в виду, что PHP не оптимизирует рекурсивные функции, даже если вы пишете их для выполнения хвостовых вызовов, а рекурсивные функции в целом менее эффективны и медленнее, чем их итеративные аналоги, хотя иногда они выполняют работу лучше, как показано в примерах кода выше , Рекурсия обычно является предпочтительной альтернативой итерации в функциональном программировании, и поэтому большинство функциональных языков оптимизируют рекурсивные функции.
Если вы используете XDebug, обязательно проверьте конфигурацию вашей системы. По умолчанию у вас будет ограничение в 100 рекурсивных вызовов, и если вы превысите его, ваш скрипт выдаст ошибку «максимальный вложенный лимит достигнут». Вы можете обновить debug.max_nesting_level конфигурации debug.max_nesting_level если вам нужно это изменить.
Наконец, полезно прочитать объяснение кучи стека и рекурсии, вызывающей переполнение стека, чтобы понять, что происходит со стеком вызовов во время рекурсии.
Вывод
В этой статье я подробно рассмотрел рекурсию и ее сравнение с итерацией. Я также покажу вам, как писать рекурсивные функции, когда их писать и почему. Я также пытался предупредить вас о некоторых подводных камнях, с которыми вы можете столкнуться при использовании рекурсии.
Рекурсия такова, что даже многие опытные программисты могут годами не пользоваться ею, а многие другие даже не слышали о ней, что печально, потому что это действительно мощная концепция. Я надеюсь, что в этой статье я мог бы дать вам достаточно знаний, чтобы выйти и начать писать свои собственные рекурсивные функции. Но помните, что, как и в случае с огнем, вы всегда должны быть осторожны и использовать инструмент с умом.
Изображение Александра Дюре-Лутца через Flickr