Что такое рекурсия » Функции » Библиотека » WAP.ZUGDIDI.US
Привет прохожий!
На главную | Вход | Регистрация

Что такое рекурсия

Рекурсией называется такая конструкция, при которой функция вызывает саму себя. Различают прямую и косвенную рекурсии. Функция называется прямо рекурсивной, если содержит в своем теле вызов самой себя. Если же функция вызывает другую функцию, которая в свою очередь вызывает первую, то такая функция называется косвенно рекурсивной.

Рассмотрим классические примеры использования рекурсии - реализацию операции возведения в степень и вычисление факториала числа. Заметим, что эти примеры являются классическими только из-за их удобства для объяснения понятия рекурсии, однако они не дают выигрыша в программной реализации по сравнению с итерационным способом решения этих задач.
<?
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 2 >>

Перейти к странице:

Комментарии (0)
Скачать Java книгу

» Функции
» Учебник по PHP
» WEB/WAP мастеру
» В библиотеку

На главную
WAP.ZUGDIDI.US
Соглашение о Предоставлении Услуг

li WAPSTART

Cжатие 63.3%