ДОБРО ПОЖАЛОВАТЬ НА САЙТ PHPLIST Всё о PHP |
Написать письмо авторам |
Что такое рекурсияРекурсией называется такая конструкция, при которой функция вызывает саму себя. Различают прямую и косвенную рекурсии. Функция называется прямо рекурсивной, если содержит в своем теле вызов самой себя. Если же функция вызывает другую функцию, которая в свою очередь вызывает первую, то такая функция называется косвенно рекурсивной. Рассмотрим классические примеры использования рекурсии - реализацию операции возведения в степень и вычисление факториала числа. Заметим, что эти примеры являются классическими только из-за их удобства для объяснения понятия рекурсии, однако они не дают выигрыша в программной реализации по сравнению с итерационным способом решения этих задач. <? function degree($x,$y) { if($y) { return $x*degree($x,$y-1); } return 1; } echo(degree(2,4)); // выводит 16 ?> Этот пример основан на том, что xy эквивалентно x*x(y-1). В этом коде задача вычисления 24 разбивается на вычисление 2*2³. Затем 2*2³ разбивается на 2*2² и так до тех пор, пока показатель не станет равным нулю. Итерационный вариант этого примера выглядит так: <? function degree($x,$y) { for($result = 1; $y > 0; --$y) { $result *= $x; } return $result; } echo(degree(2,4)); // выводит 16 ?> Кроме того, что этот код намного легче понять, он еще и более эффективен, поскольку проход цикла обходится "дешевле" вызова функции. <? function fact($x) { if ($x < 0) return 0; if ($x == 0) return 1; return $x * fact($x - 1); } echo (fact(3)); // выводит 6 ?> Для отрицательного аргумента функция возвращает нулевое значение, так как факториал отрицательного числа не существует по определению. Для нулевого параметра функция возвращает значение 1, поскольку 0! = 1. В иных случаях вызывается та же функция с уменьшенным на 1 значением параметра, после чего результат умножается на текущее значение параметра. Т. е. происходит вычисление произведения: k * (k - 1) * (k - 2) * ... * 3 * 2 * 1 * 1 Последовательность рекурсивных вызовов прерывается только при вызове fact(0), который и приводит к последнему значению 1 в произведении, так как последнее выражение, из которого вызывается функция, имеет вид 1 * fact(1 - 1). Итерационно факториал можно вычислить так: <? function fact($x) { for ($result = 1; $x > 1; --$x) { $result *= $x; } return $result; } echo (fact(6)); // выводит 720 ?>
|
Наверх |