Данный урок посвящен рекурсии в PHP. Из функции можно вызывать другую функцию. Программа может вызвать функцию f1(), которая вызывает функцию f2(), и т.д. Вызывающая себя функция называется рекурсивной. Такой тип рекурсии называется явной рекурсией. Если функция f1() вызывает другую функцию f2(), которая в свою очередь вызывает функцию f1(), то эти функции также рекурсивные. Такой тип рекурсии называется неявной рекурсией. Очевидно, что возможны более сложные формы неявной рекурсии.
Предположим, что для решения некоторой задачи нужно создать рекурсивную функцию. В этом уроке опишем одну из известных стратегий решения задачи с использованием рекурсивной функции. Процесс рекурсивного решения задачи разделяется на этапы. На первом шаге для решения задачи вызывается рекурсивная функция. В этой функции задача решается для простейшей ситуации. Простейшая ситуация данной задачи называется базисной задачей. Если функция используется для решения базисной задачи, то она возвращает решение или результат.
Если функция вызывается для решения задачи более сложной, чем базисная задача, то функция разделяет задачу на две части:
- часть 1, которую функция может решить;
- часть 2, которую функция не может решить.
Для применения рекурсии часть 2 должна быть подобна начальной задаче, но относительно меньше или проще.
Так как образовавшаяся в части 2 задача подобна начальной задаче, поэтому функция вызывает новый собственный экземпляр с целью обработки новой задачи. Это действие называется рекурсивным вызовом или шагом рекурсии.
Так как на каждом шаге рекурсии (при каждом рекурсивном вызове) задача делится на две части, поэтому то количество этих шагов рекурсии может быть достаточно большое.
Для завершения рекурсии рекурсивная функция должна образовать последовательность упрощающихся (уменьшающихся) задач, которые приближаются к базисной задаче. Когда, на каком-то шаге рекурсии, функция обнаруживает базисную задачу, она возвращает решение (результат) базисной задачи в предыдущий вызов (предыдущий шаг рекурсии). В этом вызове, в свою очередь, полученный результат объединяется с частью, которую функция может решить. Образовавшееся таким путем решение возвращается на шаг выше, и т.д. Так генерируется последний результат, который возвращается в начальную точку вызова рекурсивной функции. То есть, чтобы был возможен возврат, каждый шаг функции нужно строить таким образом, чтобы он содержал в себе зарезервированное слово return.
Для демонстрации вышеизложенной идеи приведем пример использования рекурсивной функции.
Пример 1. Факториал. Факториал целого неотрицательного числа n равен n*(n-1)*(n-2)*…2*1 и обозначается n!. Принято, что 1!=1 и 0!=1. Например, 7!=7*6*5*4*3*2*1=5040.
Итеративное (нерекурсивное) решение для вычисления факториала таково (файл factorial1.php):
<html>
<head>
<title>Факториал</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<body>
<h1>Вычисление факториала</h1>
<form action="factorial1.php" method="get">
<p>Адади натурали (n>=0): <input type="text" name="n" /></p>
<p><input type="submit" value="Вычислить"/></p>
</form>
<?php
if(!isset($_GET['n']) || ($n = $_GET['n'])=='') {
echo "Введите натуральное число!<br>";
exit;
}
$f=1;
for($i=$n;$i>=1;$i--)
$f*=$i;
echo "$n!=$f";
?>
</body>
</html>
Пусть f(n)=n!, тогда
f(n)=n!=n*(n-1)!=n*f(n-1),
то есть рекурсивная формула вычисления факториала такова:
f(n)=n*f(n-1).
Пример:
f(5)=5*f(4)=5*4*f(3)=5*4*3*f(2)= 5*4*3*2*f(1)= 5*4*3*2*1=120.
На основе рекурсивной формулы составим рекурсивную функцию для вычисления факториала (файл factorial2.php):
<html>
<head>
<title>Факториал</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<body>
<h1>Вычисление факториала</h1>
<form action="factorial2.php" method="get">
<p>Адади натурали (n>=0): <input type="text" name="n" /></p>
<p><input type="submit" value="Вычислить"/></p>
</form>
<?php
if(!isset($_GET['n']) || ($n = $_GET['n'])=='') {
echo "Введите натуральное число!<br>";
exit;
}
$f=factorial($n);
echo "$n!=$f";
function factorial($i) {
if($i<2) return 1;
$k=$i*factorial($i-1);
return $k;
}
?>
</body>
</html>
Если в программу ввести число 5, то для вычисления 5! программа действует следующим образом:
При первом вызове функции factorial() проверяется является ли посланное функции число меньше 2. Если полученное функцией число не меньше 2, то задача больше или сложнее базисной задачи, следовательно, задача делится на две части:
- $k=$i* — часть 1, которую функция может решить;
- factorial($n-1) – часть 2, которую функция не может решить.
Это действие повторяется до получения базисной задачи, то есть до вызова factorial(1). Если число меньше 2 (1 или 0), то функция factorial() возвращает число 1 ($k=1), то есть решается базисная задача. Если данный экземпляр функции factorial() был вызван ранее другим экземпляром функции factorial(), то результат возвращается вызвавшему экземпляру функции. Там возращенный результат $k умножается на переданный функции параметр $n и присваивается $k. Если данный экземпляр функции factorial() был вызван ранее другим экземпляром функции factorial(), то результат возвращается вызвавшему экземпляру функции и описанный процесс повторяется. Если данный экземпляр функции factorial() был вызван из главной части программы, то $k возвращается в эту часть, где результат выводится на экран и работа программы завершается.