Рекурсия функции в C++

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

#include <iostream>

int num = 1;

void func() {
	std::cout << num << "\n";
	num++;

	if (num <= 10) {
		func();
	}
}

int main() {
	func();
	return 0;
}

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

У нас есть глобальная переменная num и функция func. Внутри функции в консоль выводится значение num, а затем делается ++.

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

Функция будет вызывать сама себя, пока num не станет больше 10. Когда num уже больше 10, это базовый случай: новый вызов уже не делается.

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

Запишем функцию fact для факториала небольших натуральных чисел. Для 0 и 1 сразу вернем 1, иначе умножим num на факториал num - 1. В примере возьмем 5: факториал больше 12 уже не помещается в int.

#include <iostream>

int fact(int num) {
	if (num <= 1) {
		return 1;
	}

	return num * fact(num - 1);
}

int main() {
	std::cout << fact(5) << "\n";
	return 0;
}

Так же можно сложить числа от 1 до n. Базовый случай - 0, тогда сумма пустая. Иначе к num прибавляют сумму до num - 1:

#include <iostream>

int func(int num) {
	if (num <= 0) {
		return 0;
	}

	return num + func(num - 1);
}

int main() {
	std::cout << func(5) << "\n";
	return 0;
}

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

Сначала без рекурсии выведем элементы по очереди. Берем первый элемент и удаляем его из копии: вектор становится короче.

#include <iostream>
#include <vector>

void func(std::vector<int> arr) {
	std::cout << arr[0] << "\n"; // выведет 1
	arr.erase(arr.begin()); // осталось 2, 3

	std::cout << arr[0] << "\n"; // выведет 2
	arr.erase(arr.begin()); // осталось 3

	std::cout << arr[0] << "\n"; // выведет 3
	arr.erase(arr.begin()); // вектор пуст
}

int main() {
	std::vector<int> arr = {1, 2, 3};
	func(arr);
	return 0;
}

Первый элемент выводится и пропадает из копии вектора, а сам вектор уменьшается на этот элемент.

Давайте теперь используем рекурсию. Пустой вектор - базовый случай, новый вызов при нем уже не делается:

#include <iostream>
#include <vector>

void func(std::vector<int> arr) {
	if (arr.empty()) {
		return;
	}

	std::cout << arr[0] << "\n";
	arr.erase(arr.begin());

	if (!arr.empty()) {
		func(arr);
	}
}

int main() {
	std::vector<int> arr = {1, 2, 3};
	func(arr);
	return 0;
}

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

С помощью рекурсии выведите числа от 1 до 5 в консоль, по одному на строку.

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

Дан вектор:

std::vector<int> arr = {1, 2, 3, 4, 5};

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