Введение в рекурсию

Часть раздела Логика и управление потоком путешествия по C++ на Coddy — урок 45 из 56.

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

Каждая рекурсивная функция должна иметь два основных компонента. Базовый случай — это условие, которое останавливает рекурсию; без него функция вызывала бы саму себя бесконечно. Рекурсивный шаг — это этап, на котором функция вызывает саму себя с измененными параметрами, с каждым вызовом приближаясь к базовому случаю.

Вот простой пример обратного отсчета, который демонстрирует рекурсию:

void countdown(int n) {
    if (n <= 0) {           // Базовый случай: остановка, когда n достигает 0
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Рекурсивный шаг: вызов с n-1
}

Когда вы вызываете countdown(3), она выводит 3, затем вызывает countdown(2), которая выводит 2, затем вызывает countdown(1), и так далее, пока не достигнет базового случая. Каждый вызов функции ожидает завершения следующего перед своим завершением, создавая цепочку вызовов, которая в конечном итоге разворачивается обратно к исходному вызывающему объекту.

Шпаргалка

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

Каждой рекурсивной функции необходимы:

Базовый случай: условие, которое останавливает рекурсию
Рекурсивный шаг: функция вызывает саму себя с измененными параметрами

Пример функции обратного отсчета:

void countdown(int n) {
    if (n <= 0) {           // Базовый случай
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Рекурсивный шаг
}

Попробуйте сами

В этом уроке нет задания по программированию.