Что такое рекурсия и как она работает?

Рекурсия ~ [ wwweb.uz ]

В программировании, благодаря функциям, существует такое понятие, как рекурсия. Сама функция так и называется — рекурсивная функция.
Рекурсивная функция — это функция, которая вызывает саму себя.

Хорошей считаетя рекурсия, которая имеет условие для выхода, иначе получается бесконечный цикл.

// бесконечный цикл
function Rekursia() {
  Rekursia();
}

Rekursia();

// с условием выхода из рекурсии
// на примере вычисления факториала числа
// N! — произведение всех натуральных чисел от 1 до n включительно: 5!=1*2*3*4*5.

function Factorial($n)
{
  if ($n <= 1) return 1;

  // здесь происходит повторный вызов функции
  return $n * Factorial($n - 1);
} 
echo factorial(5); // 120

Программа «Средство отправки отчетов об ошибках» неожиданно завершила работу. Отправить отчет об этой ошибке?

О плюсах (+) рекурсии:

  • делает код более понятным (читабельным),
  • защищает от ошибок типа «не объявлена переменная» и пр.,
  • облегчает контроль корректности входных данных,
  • позволяет читать код с любого места, не просматривая всю страницу, отслеживая все изменения переменной,
  • облегчает отладку,
  • компактность записи кода.

О минусах (-) рекурсии:

  • рекурсия расточительна к памяти,
  • не удобна для использования в «сложной и тяжелой» логике, когда количество итераций велико (особенно для новичков),
  • переполнение стека (Stack), при плохо организованной рекурсии.

Применение рекурсии:

  • Рекурсия используется с целыми (натуральными) числами,
  • Она полезна, когда нужно выполнить перебор значений,
  • В математических задачах (напр. факториал числа),
  • При переборе содержимого каталога (для вывода дерева категорий/папок),
  • К сведению, — rar и zip (нужно зайти в папку => внутри еще папка => внутри еще папка),
  • Чтобы исключить неоднократный повторный вызов функции.

И на последок, одна особенность рекурсии в PHP. Была задачка, вывести числа от нуля до скольки-то. Код выглядит следующим образом:

function numbers(int $x) {
    if ($x == 0) {
        echo $x;
        return;
    }
    numbers($x - 1);
    echo ', ' . $x;
}
numbers(3); // 0, 1, 2, 3

Как видно результатом будет вывод чисел от 0 до 3, а не с конца.
Строка '$x-1' работает же на уменьшение от большего к меньшему?

Всё дело в том, что рекурсия в PHP выполняя проход по циклу собирает результаты в стек, как стопка книг, заполняя его снизу вверх.
А затем, когда граничное условие выполнено, начинает возвращать результат, но теперь уже берет значения с конца, т.е. с верхней части стопки книг (стека).
Получается, что заполнение идет 3, 2, 1, 0, а выборка идет в обратном порядке. Этот подход называется LIFO (Last in — First out, последним зашел — первым вышел).

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *