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

Любая рекурсивная функция должна иметь два компонента:

1. Условие выхода (базовый случай): точка, где вызовы прекращаются. Без неё возникнет бесконечный цикл и ошибка переполнения стека.
2. Рекурсивный шаг: вызов функцией самой себя с измененными аргументами.

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

Теперь функция работает так, как было задумано. Это выглядит примерно так:

Стек

Концепция стека вызовов играет важную роль в программировании вообще; кроме того, ее важно понимать при использовании рекурсии.

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

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

Внутри этой функции ты вызываешь другую функцию. PHP снова кладет новый уровень в стек. И так далее. Получается цепочка вызовов, вложенная друг в друга.

Когда функция заканчивается (return или просто конец функции), PHP снимает верхний уровень стека и возвращается туда, откуда пришел. Потом еще раз. Пока не вернется в самый низ, в основной файл.

def greet(name):
    print("hello, " + name + "!")
    greet2(name)
    print("getting ready to say bye...")
    bye()

// Call
greet("Alex")

Шаги выполнения

Шаг	Выполняемая строка	Что происходит	Состояние стека
1	greet("Alex")	старт программы, вызов greet	[ main -> greet ]
2	print("hello, Alex!")	вывод строки	[ main -> greet -> print ]
3	возврат из print	print закончил работу	[ main -> greet ]
4	greet2(name)	вызов greet2	[ main -> greet -> greet2 ]
5	возврат из greet2	greet2 завершилась	[ main -> greet ]
6	print("getting ready to say bye...")	вывод строки	[ main -> greet -> print ]
7	возврат из print	print закончил работу	[ main -> greet ]
8	bye()	вызов bye	[ main -> greet -> bye ]
9	возврат из bye	bye завершилась	[ main -> greet ]
10	конец greet	функция закончилась	[ main ]

Очень важно понять это:

• Пока greet2 или bye выполняются, код greet стоит на паузе. Он не исчезает, не “идет параллельно”. Он буквально заморожен в стеке и ждет, пока верхний вызов завершится.
• PHP помнит, где он сейчас находится в коде и как туда вернуться. Он знает, что мы пришли из функции greet и что туда надо будет вернуться.
• Все вызовы функций сохраняются в стеке вызовов.
• Когад функция заканчиваетя выполнение, она пропадает из стека.

Стек вызовов с рекурсией

Рекурсивные функции тоже используют стек вызовов! Посмотрим, как это делается , на примере функции вычисления факториала. Вызов factorial(5) записывается в виде 5! и определяется следующим образом: 5! = 5*4*3*2*1.
По тому же принципу factorial(З) соответствует 3*2*1. Рекурсивная функция для вычисления факториала числа выглядит так:

В программу включается вызов fact(З). Проанализируем этот вызов строку за строкой и посмотрим, как изменяется стек вызовов. Стоит напомнить, что верхний блок в стеке сообщает, какой вызов fact является текущим.

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

Очень важно: рекурсия делает два этапа: сначала “спуск” (наращиваем стек), потом “подъем” (разматываем стек и считаем).

Фишка рекурсии: каждая функция “зависает” на строчке return $n * fact($n-1); пока нижний вызов не вернет число. Именно это и хранит стек: кто ждет чего и где продолжать выполнение. Мы ждем пока самый последний вызов функции вернет 1 и начинаем подниматься вверх и умножать.

Шаг	Текущий вызов	Что происходит	Стек вызовов	Возвращаемое значение
1	fact(3)	вызов функции, n=3	[ main -> fact(3) ]	—
2	fact(3)	нужно посчитать 3 * fact(2)	[ main -> fact(3) ]	—
3	fact(2)	рекурсивный вызов	[ main -> fact(3) -> fact(2) ]	—
4	fact(2)	нужно посчитать 2 * fact(1)	[ main -> fact(3) -> fact(2) ]	—
5	fact(1)	рекурсивный вызов, база	[ main -> fact(3) -> fact(2) -> fact(1) ]	—
6	fact(1)	база, сразу return 1	[ main -> fact(3) -> fact(2) ]	1
7	fact(2)	получили 1, считаем 2 * 1	[ main -> fact(3) -> fact(2) ]	2
8	fact(2)	return 2, выходим	[ main -> fact(3) ]	2
9	fact(3)	получили 2, считаем 3 * 2	[ main -> fact(3) ]	6
10	fact(3)	return 6, выходим	[ main ]	6

Первые шаги это спуск. Мы только накапливаем вызовы и ничего не считаем по-настоящему.
Начиная с fact(1) начинается подъем. Значения возвращаются вверх, стек сжимается, и каждый уровень домножает свое число.

Ключевая мысль.
Рекурсивная функция всегда сначала строит стек (функции кладутся в стек как тарелки) , а потом его разматывает.

Важно:

• самая глубокая функция не вызывается первой
• она первой возвращает результат

Почему возникает ощущение, что она “первая”?

Потому что до базы ничего не считается. Все функции “висят” на паузе, ожидая результат снизу.

<?php

function factorial($n) {
	
	if ($n == 1) return 1;
	
	/*Когда получили 1, выходим с функции factorial(1), и по стеку вызовов поднимаемся вверх.
	Попадем на factorial(2), на возвращает "return $n * factorial($n - 1)", так как factorial($n - 1) вернул 1,
	значит умножаем 2 * 1.
	
	Поднимаемся по стеку вверх. Теперь factorial(3), factorial(2) вернул 2, поэтому делаем 3*2=6
	*/
	
	 return $n * factorial($n - 1);
}

$result = factorial(5);

var_dump($result);