Рекурсия в Dart

В программировании есть такое понятие, как рекурсия - это когда функция вызывает сама себя. Давайте посмотрим на примере. Выведем с помощью рекурсии числа от 1 до 10:

var i = 1;

void func() {
	print(i);
	i++;

	if (i <= 10) {
		func(); // здесь функция вызывает сама себя
	}
}

void main() {
	func();
}

Давайте обсудим, как работает этот код.

У нас есть переменная i верхнего уровня и функция func. Внутри функции на экран выводится содержимое переменной i, а затем делается ++.

Если наша переменная i меньше или равна 10, то функция вызывается повторно. Так как переменная i объявлена на верхнем уровне, при каждом новом вызове функции в ней будет значение, заданное при предыдущем вызове.

Получится, что функция будет вызывать сама себя до тех пор, пока i не станет больше 10.

Учтите, что в нашем случае нельзя функцию запустить без if - если это сделать, то получится бесконечный вызов функций.

Давайте с помощью рекурсии последовательно выведем элементы списка. Пусть список изначально передается параметром функции:

void main() {
	func([1, 2, 3]);
}

Давайте пока без рекурсии. Метод removeAt вырезает и возвращает элемент по индексу, а сам список уменьшается на этот элемент. Выведем элементы списка по очереди:

void func(List<int> arr) {
	print(arr.removeAt(0)); // выведет 1
	print(arr); // выведет [2, 3] - список уменьшился

	print(arr.removeAt(0)); // выведет 2
	print(arr); // выведет [3] - список уменьшился

	print(arr.removeAt(0)); // выведет 3
	print(arr); // выведет [] - список пуст
}

void main() {
	func([1, 2, 3]);
}

Как вы видите, removeAt(0) вырезает и возвращает первый элемент списка, при этом сам список уменьшается на этот элемент.

Давайте теперь используем рекурсию:

void func(List<int> arr) {
	print(arr.removeAt(0));
	print(arr);

	if (arr.length != 0) {
		func(arr);
	}
}

void main() {
	func([1, 2, 3]);
}

На самом деле проще всего перебрать элементы списка циклом. Приведенные примеры пока просто демонстрируют работу рекурсии на простых примерах.

Дана карта:

var arr = {"a": 1, "b": 2, "c": 3, "d": 4, "e": 5};

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