Опубликовано:

Все рекурсивные функции в PHP

Источник: «All the recursive Functions in PHP»
Рекурсивная функция — это функция, вызывающая саму себя для решения задачи. Этот тип функций часто используется в ситуациях, когда задачу можно разбить на более мелкие, похожие, но всё же более мелкие задачи. Функция продолжает вызывать себя с изменёнными аргументами до тех пор, пока не будет достигнут базовый случай, после чего функция перестаёт вызывать себя и начинает возвращать значения. Итак, все ли рекурсивные функции в PHP нам известны?

Оглавление

В этой статье мы рассмотрим различные формы, которые могут принимать рекурсивные PHP функции. Начнём с классических жёстко закодированных рекурсивных функций и методов; расширенных косвенных рекурсивных функций; неуловимых рекурсивных замыканий и стрелочных функций; и, наконец, хитрых абстрактных рекурсивных функций.

Кто бы мог подумать, что рекурсивные функции могут быть настолько метаморфозными!

Рекурсивные функции

Рекурсивные функции — это самая простая форма. Это функция, которая содержит вызов самой себя. Классически она представлена для вычисления факториалов: n!, читается факториал n: факториал — это произведение всех целых чисел от 1 до n, включительно. С рекурсией это выглядит следующим образом:

<?php

function factorial(int $n) : int {
  if ($n <= 1) { return 1; }
  return $n * factorial($n - 1);
}

print factorial(4); // 4! = 1 * 2 * 3 * 4 = 24

?>

Чтобы вычислить факториал 4, функция выполняет произведение между 4 и факториалом 3. В свою очередь, этот факториал вычисляется со значением факториала 2; этот цикл останавливается, когда factorial() достигает 1, где возвращает 1: это базовый случай.

Рекурсия основана на обращении к себе: вы можете увидеть вызов factorial внутри тела той же функции factorial.

Также важно отметить, что этот вызов функции самой себя должен контролироваться условием: роль условия заключается в том, чтобы предотвратить бесконечный цикл, пропуская вызов функции самой себя в определённых ситуациях. Здесь вычисляется меньший факториал, пока он не достигнет 1 или меньше. Тогда он безоговорочно возвращает 1.

Рекурсивные методы

Рекурсивные методы очень близки к рекурсивным функциям. Нужно только вызвать себя, и, используя псевдопеременную $this, легко найти подходящий объект для этого вызова. Предыдущая функция factorial превращается в следующую:

<?php

class Factorial {
    function calculate(int $n) : int {
        if ($n <= 1) { return 1; }
        return $n * $this->calculate($n - 1);
    }
}

$factorial = new Factorial();
print $factorial->calculate(4); // 4! = 1 * 2 * 3 * 4 = 24

?>

Рекурсивные распределённые методы

Использование $this — не единственная возможность сделать рекурсивный вызов. Предыдущий код может не использовать $this, полагаясь на другой объект для передачи вызовов.

<?php

class Factorial {
    function calculate(int $n) : int {
        if ($n <= 1) { return 1; }

        $that = new self();
        return $n * $that->calculate($n - 1);
    }
}

$factorial = new Factorial();
print $factorial->calculate(4); // 4! = 1 * 2 * 3 * 4 = 24

?>

Наше первоначальное определение рекурсии, основанное на вызове самого себя, по-прежнему применимо. Приведённый выше код является рекурсивной функцией, поскольку Factorial::calculate() вызывает сам себя. Однако каждый раз она вызывается на разных объектах, поэтому она также немного отличается.

Нам не удалось найти реального применения такого представления рекурсии. Тем не менее это интригующее открытие.

Косвенно рекурсивные функции

Функции, которые мы представили до сих пор, являются прямо рекурсивными: они напрямую вызывают сами себя. Кроме того, существуют и косвенно рекурсивные функции. Главное отличие заключается в том, что они вызывают другие функции, которые в конечном итоге вызывают их обратно.

<?php

function even(int $i) {
    return $i * odd($i - 1);
}

function odd(int $i) {
     if ($i === 1) { return 1;}
   return $i * even($i - 1);
}

$n = 4;
if ($n % 2) {
    print even($n); // в данном случае не используется
} else {
    print even($n); // 4! = 1 * 2 * 3 * 4 = 24
}

?>

В этом коде факториал распределён между двумя отдельными функциями. Одна из них обрабатывает нечётные числа, а другая — чётные. Поскольку начальные значения практически не проверяются, важно хорошо выбрать начальный вызов. Это непрактично, но иллюстрирует случай косвенной рекурсии.

При вычислении факториала 4 сначала вызывается функция even(), которая вызывает odd(), затем снова even(), затем odd() и, наконец, всё перемножается.

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

Косвенная рекурсия на практике встречается очень редко. Это хитрая и нестабильная структура, которую довольно сложно правильно реализовать. Тем не менее это происходит путём простого органического роста, когда методы вызывают друг друга до тех пор, пока один из них не вызовет снова первый и не спровоцирует бесконечный цикл. Остаётся надеяться, что это будет обнаружено на ранней стадии разработки.

Рекурсивные замыкания

Функции и методы могут быть рекурсивными с помощью простого вызова самих себя. С замыканиями это становится сложной задачей, поскольку они анонимны: у них нет имени, которое можно было бы использовать для вызова самого себя. Это довольно сложная задача, и, тем не менее, PHP может её решить.

<?php

$factorial = function (int $n) use (&$factorial)  : int {
        if ($n <= 1) { return 1; }
        return $n * $factorial($n - 1);
};

print $factorial(4); // 4! = 1 * 2 * 3 * 4 = 24

?>

Без имени замыкание должно вызываться с переменной, которая содержит саму себя. Таким образом, чтобы быть рекурсивным, замыкание должно получать переменную, которая содержит саму себя. Такова роль переменной $factorial в выражении use. Позже она используется в теле для вызова самой себя.

Одна из деталей — ссылка &, добавленная к $factorial. Действительно, она здесь необходима, и без неё замыкание не будет работать. Без неё оно выдаёт ошибку Undefined variable $factorial.

Хотя это выглядит странно, это нормальный феномен. Сначала строится замыкание, затем оно присваивается переменной $factorial. Замыкание собирает переменные из текущей области видимости с выражением use и включает их в свою область видимости. В данном случае переменная $factorial находится слева от присваивания, поэтому она будет создана после самого замыкания. Следовательно, она недоступна для сбора во время определения замыкания.

Поскольку замыкание должно включать само себя, ссылка необходима. Ссылка заставляет PHP создать переменную $factorial без содержимого (или NULL); она также сохраняет обращение к этой переменной. Позже, после определения замыкания, замыкание присваивается $factorial, что приводит к его включению в замыкание.

Если создать переменную $factorial до замыкания, но не использовать на ссылку на неё, она сохранит своё предыдущее значение и не будет инжектирована в замыкание. Это не работает.

Рекурсивное замыкание с параметром

Также можно использовать параметры для инъекции замыкания и сделать его рекурсивным. В этом случае не нужно использовать ссылку. С другой стороны, необходимо добавлять замыкание во все вызовы. Повторение оправдано и немного удивляет.

<?php

$factorial = function (int $n, $factorial) : int {
        if ($n <= 1) { return 1; }
        return $n * $factorial($n - 1, $factorial);
};

print $factorial(4, $factorial); // 4! = 1 * 2 * 3 * 4 = 24

?>

Рекурсивные стрелочные функции

С рекурсивными стрелочными функциями сложность возрастает. Фокус теперь в том, что больше нет условия use, поэтому невозможно сделать ссылку, содержащую саму стрелочную функцию. Фактически, невозможно сделать ссылку на стрелочную функцию, поскольку она фактически является объектом Closure и сама является ссылкой.

<?php

// Parse error: syntax error, unexpected token "fn"
$factorial = &fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);

?>

В приведённом выше коде PHP не может различить, возвращает ли стрелочная функция ссылку или $factorial назначается ссылкой на стрелочную функцию.

Если переменная $factorial создаётся до стрелочной функции, то стрелочная функция забирает её предыдущее значение: это не рекурсивная стрелочная функция. В приведённом ниже коде стрелочная функция использует целое число 1, которое доступно до определения стрелочной функции.

<?php

$factorial = 1;
$factorial = fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);

//Fatal error: Uncaught Error: Value of type int is not callable

?>

Одно из преимуществ стрелочной функции перед Closure (см. предыдущие разделы) заключается в том, что стрелочная функция проверяет содержимое переменной только во время выполнения. Таким образом, можно повторить определение стрелочной функции и сделать её пригодной для решения факториальной задачи. Конечно, здесь есть загвоздка:

<?php

$factorial = 1;
$factorial = fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);
$factorial = fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);
$factorial = fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);
$factorial = fn (int $n) : int => $n <= 1 ? 1 : $n * $factorial($n - 1);

print $factorial(4); // 4! = 1 * 2 * 3 * 4 = 24

?>

При каждом повторении $factorial может сделать дополнительный вызов предыдущей копии себя. Таким образом, чтобы вычислить 4!, определение стрелочной функции должно быть продублировано 4 раза. Это приводит к (почти) рекурсивной косвенной функции уровня 4, хотя последняя стрелочная функция на самом деле умирает и не используется.

В итоге единственным решением для рекурсивных стрелочных функций является использование синтаксиса аргументов.

<?php

$factorial = fn (int $n, $factorial) : int => $n <= 1 ? 1 : $n * $factorial($n - 1, $factorial);

print $factorial(4, $factorial); // 4! = 1 * 2 * 3 * 4 = 24

?>

Абстрактно рекурсивные функции

В завершение давайте вернёмся к нашему первоначальному определению рекурсивной функции: это была функция, которая вызывает сама себя. Мы смогли сделать рекурсивные версии всех типов функций PHP. Теперь давайте посмотрим на последний код (приведённый выше) с небольшими изменениями:

<?php

$factorial = fn (int $n, $foo) : int => $n <= 1 ? 1 : $n * $foo($n - 1, $foo);

print $factorial(4, $factorial); // 4! = 1 * 2 * 3 * 4 = 24

?>

Как только имя параметра $factorial становится $foo, рекурсивный характер стрелочной функции исчезает: это уже не так очевидно, как раньше. В самом деле, при вызове стрелочной функции мы могли бы использовать другую стрелочную функцию, и тогда стрелочная функция $factorial не стала бы рекурсивной: с другой стороны, её параметр $foo стал бы таковым.

<?php

$factorial = fn (int $n, $foo) : int => $n <= 1 ? 1 : $n * $foo($n - 1, $foo);

// $factorial не рекурсивная
// foo() может быть рекурсивной
print $factorial(4, foo(...)); // 4! = 1 * 2 * 3 * 4 = 24

?>

При использовании вызываемого параметра для обеспечения рекурсивности функции необходимы вызов $factorial($x, $factorial) и определение метода, содержащее $factorial($x, $factorial). Только одного из них недостаточно, чтобы сделать функцию рекурсивной.

В начальных примерах с именованными функциями и методами жёстко закодированный характер вызова позволяет с уверенностью определить, что они рекурсивны. В случае с анонимными структурами, такими как замыкания и стрелочные функции, использование этих функций также важно учитывать. В противном случае их рекурсивный характер является лишь абстрактным понятием.

Рекурсивный зоопарк в PHP

Все рекурсивные функции в PHP образуют довольно большой зоопарк:

Интересно осознавать, насколько разнообразны и сложны скромные рекурсивные функции в PHP. Они создают проблемы с анонимными функциями, распределёнными и косвенно рекурсивными функциями, и даже включают параметры времени вызова в своё определение. Тем не менее они являются неотъемлемой частью мира PHP: 44% проектов используют их.

И помните, что рекурсивность заключается в самом названии PHP!

Предыдущая Статья

Процессы и команды Artisan в Laravel

Следующая Статья

Использование $fillable для валидации