PHP скрипты

MySQL

Apache

phpMyADmin

Навигация

Поиск по Сайту

Партнеры

Самоучитель. Книги.

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. Причем это значение возвратится не в основную программу, а в тело предыдущей функции. Эта функция, в свою очередь, возвратит свое значение в тело следующей функции и т. д., пока нужное значение не возвратится в основную программу.

Поделиться с друзьями