Рекурсия в php

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

<?php
$arr = [
	'abc',
    [
        1,
        2
    ],
    'd',
    [
    	[
    		'e',
    		'f',
    		[
    			'g'
    		]
    	]
    ]
];

Выглядит сложно? Неправда ли? Сначала попробуйте пробежаться циклом и вывести на экран все цифры и буквы в строчку. Не получается? Это потому, что этот массив имеет много вложений. Если вы использовали функцию foreach(), то у вас не возникло сложностей пробежать по первому уровню элементов, а если вы встречали на своем пути массивы, то вам пришлось писать условие if и внутри создавать функцию foreach() снова. Но что делать если таких уровней много, более миллиона? Не будете же вы писать так много условий? Давайте по порядку. Напишем простую функцию и вызовем ее.

<?php
function my_recursion(array $arr): string
{
	foreach($arr as $value) {
		// magic
		var_dump($value);
	}
}

echo my_recursion($arr);

Здесь мы объявили нашу рекурсивную функцию. Сейчас эта функция просто пробегает по массиву и перебирает все элементы на первом уровне. Результат будет примерно такой:

string(3) "abc"
array(2) {
  [0]=>
  int(1)
  [1]=>
  int(2)
}
string(1) "d"
... и так далее ...

Как видите на второй итерации нам встретился массив с 2мя элементами. Если бы мы не знали рекурсию, мы бы написали if(is_array()) и далее начали бы его перебирать... Но мы сейчас совершим магию =)

<?php
function my_recursion(array $arr): string
{
    $string = '';
	foreach($arr as $value) {
		// magic
		if(is_array($value)) {
			$string .= my_recursion($value);
		} else {
			$string .= $value;
		}
	}
	
	return $string;
}

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

• 1 Итерация: Мы встречаем строку "abc". Наш код спрашивает. Это массив? - Нет. Значит мы с помощью конкатенации дописываем значение "abc" в $string
• 2 Итерация: Здесь у нас уже массив из 2х элементов [1,2]. Наш код спрашивает. Это массив? - Да. Далее строчка $string .= my_recursion($value); говорит нам, что нужно все значения, которые вернет функция записать в переменную $string. А в качестве аргумента мы передаем текущее $value, то есть [1,2]. Теперь функция вызывает сама себя. Мы снова получаем пустой $string. Снова перебираем наш массив и делаем проверку is_array. На первом шаге у нас число 1. Это массив? - нет. Значит мы дописываем в переменную $string = 1. Следующее число 2. Это также не массив. А значит мы дописываем к единице 2ку. Цикл кончился и мы переходим к return $string, то есть возвращаем "12". Но "прошлая" функция еще не закончила свою работу. И мы находим на строчке $string .= my_recursion($value); где к переменной $string дописывается, то что вернула функция. То есть будет равно $string = "abc12"

Я думаю смысл вы уловили. Дальше код идет к 4ей итерации и так далее. И каждый раз когда он будет встречать массив, он будет запускать саму себя снова и снова и записывать значения в $string. А когда все итерации "отыграют" он в конце вернет значения $string, где будут все элементы массива.