7.6: Рекурсия в PHP
Главная Страница » Книги по PHP » Самоучитель PHP 5 для чайников с примерами » Рекурсия
При объяснении решения задач математики очень часто применяют словосочетание «по индукции», которое многих ставит в тупик, так как это понятие является не самым простым. В программировании тоже имеется своеобразная индукция, называемая рекурсией.
Например, попробуем написать функцию с помощью обычного цикла for, возвращающую факториал числа. Из курса математики известно, что он вычисляется следующим образом: n! =1*2...*(n-1 )*n. Причем 0!=1, а факториала отрицательных чисел не бывает (листинг 7.13).
Листинг 7.13. Функция нахождения факториала числа без рекурсии.
‹html›
‹head›
‹title›Функция нахождения факториала числа без рекурсии‹/title›
‹/head›
‹body›
‹?php
function factorial($num)
{
if ($num < 0)
{
return 0;
}
if ($num == 0)
{
return 1;
}
for ($i = 1, $sum = 1; $i <= $num; $i++)
{
$sum = $sum * $i;
}
return $sum;
}
echo factorial(3); // выведет 6
?›
‹/body›
‹/html›
Итак, задача решена, как говорится, «в лоб». В случае передачи отрицательных значений функция будет возвращать 0. Это реализуется с помощью первого оператора if. Далее если передано число 0, то возвращаем единицу. И наконец, в цикле for вычисляем факториал при любых других значениях.
При решении задач с помощью рекурсии требуются рассуждения иного рода. Например, факториал числа можно вычислить следующим образом:
n! = 1, если n=0
n! = n*(n-1)!, если n>0
Заметьте, что второе утверждение содержит в себе знак факториала. Именно в этом и состоит основной смысл рекурсии. При решении определенной задачи мы используем то, что нам нужно найти. В программировании функцию называют рекурсивной, если в ее описании присутствует обращение саму на себя.
Итак, вернемся к рассуждению о факториале. При решении задач с помощью рекурсии всегда надо иметь два типа утверждений: базисное и рекурсивное. В нашем случае базисным утверждением является n! = 1, если n = 0. Как вы, наверное, уже догадались, работая с рекурсивным утверждением, мы должны перейти к базисному и получить результат. Теперь попробуем реализовать все это на практике (листинг 7.14).
Листинг 7.14. Функция нахождения факториала числа с рекурсией
‹html›
‹head›
‹title›Функция нахождения факториала числа с рекурсией‹/title›
‹/head›
‹body›
‹?php
function factorial($num)
{
if ($num < 0)
{
return 0;
}
if ($num == 0)
{
return 1;
}
return $num*factorial($num-1); // рекурсивный вывод
}
echo factorial(3); // выведет 6
?›
‹/body›
‹/html›
В этом случае первые два условия аналогичны примеру, разобранному выше. Но теперь вместо цикла fоr мы записываем рекурсивное выражение, в котором функция вызывает сама себя. В нашей программе это происходит до тех пор, пока в качестве входного параметра не будет число 0, при котором функция возвратит 1. Причем это значение возвратится не в основную программу, а в тело предыдущей функции. Эта функция, в свою очередь, возвратит свое значение в тело следующей функции и т. д., пока нужное значение не возвратится в основную программу.
