На этом шаге мы рассмотрим понятие рекурсии.
В программировании имеется понятие "рекурсия".
Например, попробуем написать функцию с помощью обычного цикла for, возвращающую факториал числа. Он вычисляется следующим образом: n!=1*2*...*(n-1)*n. Причем 0! = 1 и 1! = 1, а факториала отрицательных чисел не бывает. Напишем функцию нахождения факториала числа без рекурсии.
<?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
?>
В этом случае выводится число 6. Задача решена, как говорится, "в лоб". В случае передачи отрицательных значений функция будет возвращать 0. Это реализуется с помощью первого оператора if. Если передано число 0, то возвращаем единицу. При любых других значениях факториал вычисляем в цикле for.
При решении задач с помощью рекурсии требуются рассуждения иного рода. Например, факториал числа можно вычислить следующим образом:
n! = 1, если n = 0 и n = 1, n! = n*(n-1)!, если n>0.
Заметьте, что второе утверждение содержит в себе знак факториала. Именно в этом и состоит основной смысл рекурсии. При решении определенной задачи мы используем то, что нам нужно найти. В программировании функцию называют рекурсивной, если в ее описании присутствует обращение к самой себе.
Итак, вернемся к задаче о факториале числа. При решении задач с помощью рекурсии всегда надо иметь два типа утверждений: базисное и рекурсивное. В нашем случае базисным утверждением является n! = 1 если n = 0 или n = 1. Эти значения называются точками останова. Работая с рекурсивным утверждением, мы должны перейти к базисному и получить результат. Теперь напишем функцию нахождения факториала числа с использованием рекурсии.
<?php
function factorial ($num)
{
if ($num < 0)
{
return 0;
}
if ($num == 0)
{
return 1;
}
return $num*factorial($num-1); // рекурсивный вывод
}
echo factorial(3); // выведет 6
?>
В этом случае первые два условия взяты из предыдущего примера. Но теперь вместо цикла for мы записываем рекурсивное выражение, в котором функция вызывает сама себя. В нашей программе это происходит до тех пор, пока в качестве входного параметра не будет число 0, при котором функция возвратит 1. Причем это значение возвратится не в основную программу, а в тело предыдущей функции. Эта функция, в свою очередь, возвратит свое значение в тело следующей функции и т.д., пока нужное значение не возвратится в основную программу.
Со следующего шага мы начнем знакомиться с массивами.
