Рекурсия vs цикл: критерии выбора

1. Одна задача — две формы записи

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

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

Чтобы не улететь в философию, будем держать в голове простой ориентир: если в рекурсивной версии вы легко можете объяснить «что будет на шаге» и «как мы идём к базе», то рекурсия может быть хорошим кандидатом. Если же вы постоянно проверяете глазами, не уйдёт ли это в бесконечность, то, возможно, цикл даст более прозрачную картину.

Карта соответствий: рекурсия ↔ цикл

Когда вы переводите рекурсию в цикл (или наоборот), очень помогает не писать код «с нуля», а сопоставлять части конструкции. Это как перевод с одного языка на другой: если вы забыли слово «стол», можно сказать «то, на чём стоит кружка», но лучше всё-таки знать слово.

Ниже — удобная таблица соответствий. Её стоит держать как шпаргалку, но не как религию.

Самая частая ошибка новичка здесь — думать, что рекурсия «сама как-то оптимизируется» или «сама как-то остановится». Нет. Рекурсия останавливается только потому, что вы написали условие, при котором самовызова больше не будет. Цикл останавливается тоже только потому, что вы написали условие и обновляете переменные так, чтобы условие стало ложным. Магии нет. Есть только вы и ваша способность не потерять -1 по дороге.

2. Пример №1: факториал — две версии, один смысл

Факториал — это почти официальный талисман рекурсии. Его часто показывают первым, потому что формула сама по себе рекурсивная: n! = n * (n-1)!. Но нам важно другое: факториал отлично демонстрирует, что рекурсия и цикл здесь одинаково естественны — и можно выбирать по читаемости.

Рекурсивная версия

Сейчас мы пишем так, чтобы было максимально понятно, где база и где шаг.

#include <iostream>

long long factorial_rec(int n) {
    if (n == 0) return 1;              // базовый случай
    return n * factorial_rec(n - 1);   // рекурсивный шаг
}

Если вы читаете это вслух, всё звучит логично: «если ноль — верни 1, иначе верни n умножить на факториал n-1». Это редкий случай, когда математика и код смотрят друг на друга без взаимной ненависти.

Циклическая версия

А теперь та же логика, только без «нырка» в стек.

#include <iostream>

long long factorial_loop(int n) {
    long long result = 1;              // нейтральный элемент для умножения
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

Если вы новичок, цикл может быть даже понятнее: видно, что переменная result копит ответ, а i идёт от 2 до n. Никаких «после возврата мы домножим» — всё происходит прямо здесь, в одной плоскости реальности.

3. Пример №2: печать строки в обратном порядке

Задача: вывести строку в обратном порядке. Да, можно сделать индексный цикл назад. Но рекурсия даёт очень чистую идею: «сначала дойди до конца, потом печатай».

Ключевой момент читаемости: делаем до вызова и на возврате

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

Проблема в том, что «после рекурсивного вызова» означает: «мы это сделаем, когда начнём возвращаться назад по стеку». То есть порядок выполнения становится обратным.

Это лучше всего видно на строках.

Рекурсия: печатаем «на возврате»

#include <iostream>
#include <string>

void print_reverse_rec(const std::string& s, std::size_t i) {
    if (i == s.size()) return;     // база: дошли до конца
    print_reverse_rec(s, i + 1);   // идём глубже
    std::cout << s[i];             // печатаем на возврате
}

Если запустить это так:

int main() {
    print_reverse_rec("abcd", 0);
    std::cout << '\n';             // dcba
}

то получится dcba. И это не «магия рекурсии», это просто порядок: сначала мы дошли до i == size, а потом начали возвращаться: i = size-1, i = size-2 и так далее.

Цикл: печатаем обратным индексом

#include <iostream>
#include <string>

void print_reverse_loop(const std::string& s) {
    for (std::size_t i = s.size(); i > 0; --i) {
        std::cout << s[i - 1];
    }
}

И вызов:

int main() {
    print_reverse_loop("abcd");
    std::cout << '\n';             // dcba
}

Цикл здесь тоже отличный, просто нужно аккуратно писать границы: i > 0 и индекс i - 1. Иначе можно словить знаменитую проблему с size_t: он беззнаковый, и «ниже нуля» он уходить не умеет — он превращается в огромное число и делает вид, что так и было задумано.

Перевод рекурсии в цикл: «собираем ответ сразу» и «собираем ответ потом»

Сейчас будет мысль, которую полезно проговорить: не вся рекурсия одинаково легко переводится в цикл «в лоб». Пример факториала и суммы обычно переводится легко, потому что результат можно копить в переменной.

Но если в рекурсии основной эффект/действие стоит «на возврате», то при переводе в цикл вам часто нужно либо идти в обратном направлении, либо сначала дойти до конца, а потом обработать результат в обратном порядке.

Для строки это просто: вы умеете идти индексом назад. Для более сложных задач (например, обход структуры «в глубину») это станет интереснее, но туда мы сегодня не залезаем — нам важен сам принцип порядка выполнения.

Чтобы закрепить, посмотрим на сумму от 1 до n: там действие обычно «до вызова» (по сути), но запись выглядит как «после» из-за выражения n + sum_to(n - 1).

4. Пример №3: сумма 1..n — рекурсия и цикл

Рекурсия

#include <iostream>

int sum_to_rec(int n) {
    if (n == 0) return 0;          // база: нейтральный элемент для суммы
    return n + sum_to_rec(n - 1);
}

Цикл

#include <iostream>

int sum_to_loop(int n) {
    int sum = 0;                   // тот же смысл, что база в рекурсии
    for (int i = 1; i <= n; ++i) {
        sum += i;
    }
    return sum;
}

В обоих случаях ключевая мысль — нейтральный элемент: для суммы это 0, для произведения это 1. Если перепутать, код будет компилироваться и даже работать, просто выдавать «творческий» ответ. Иногда компилятор тоже хочет быть художником, но обычно у него не получается.

5. Критерии выбора: как решить, что писать — рекурсию или цикл

Сейчас хочется дать «универсальное правило», но честнее будет сказать: универсального правила нет. Зато есть практические критерии, которые почти всегда помогают новичку сделать хороший выбор.

Первый критерий — прозрачность остановки. В цикле вы обычно видите условие остановки в заголовке for/while. В рекурсии остановка спрятана в базовом случае, и если вы его не заметили или он не достигается, функция будет вызывать себя, пока программе не станет физически плохо. Поэтому если вы пишете рекурсию, базовый случай должен бросаться в глаза как красный флаг «СТОП».

Второй критерий — порядок действий. Если вам естественно мыслить «сначала углубляемся, потом делаем действие на возврате», рекурсия часто получается читабельнее. Пример со строкой — именно такой. Если же вам проще мыслить «в каждом шаге цикла я делаю кусочек работы», то цикл, как правило, читается легче, особенно когда есть накопительная переменная.

Третий критерий — количество движущихся частей. Иногда рекурсивная версия выглядит короткой и «математической», а циклическая обрастает индексами, границами, проверками и начинает походить на тамагочи, которого нельзя оставлять без присмотра. Иногда наоборот: рекурсивная версия требует передачи нескольких параметров, аккуратной базы и внимательного понимания, где «до», а где «после», а цикл выглядит как честные 6 строк. Выбирайте то, где меньше шансов ошибиться именно вам, на вашем текущем уровне.

Четвёртый критерий — локальность понимания. Цикл обычно читается «сверху вниз» как один поток. Рекурсия требует мысленного «раскрытия» вызовов, то есть вы должны уметь представить несколько уровней. Это навык, который прокачивается, но в начале он дорогой. Поэтому на первых порах нормально чаще выбирать циклы, если рекурсия не даёт явного выигрыша в ясности.

Чтобы зафиксировать всё это не только словами, давайте оформим «памятку выбора» в виде маленькой таблицы. Она не про скорость и память (про это будет отдельная лекция), а именно про читаемость и риск ошибок.

6. Команда reverse в нашем консольном приложении

Чтобы не превращать лекцию в набор отдельных «игрушечных» функций, давайте продолжим идею нашего простого консольного приложения, которое принимает команды и выполняет небольшие операции со строками. Мы не строим полноценный продукт (ещё рано), но тренируем главный навык: писать маленькие функции и подключать их в main.

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

Вот каркас обработчика команды:

#include <iostream>
#include <string>

void run_reverse_command() {
    std::string s;
    std::getline(std::cin, s);

    // Пока просто печатаем, позже можно будет расширить.
    // Реализацию выберем ниже.
}

Теперь добавим две функции печати (мы их уже видели, но соберём рядом, чтобы было удобно подключать).

#include <iostream>
#include <string>

void print_reverse_rec(const std::string& s, std::size_t i) {
    if (i == s.size()) return;
    print_reverse_rec(s, i + 1);
    std::cout << s[i];
}

И циклическую:

#include <iostream>
#include <string>

void print_reverse_loop(const std::string& s) {
    for (std::size_t i = s.size(); i > 0; --i) {
        std::cout << s[i - 1];
    }
}

Теперь внутри команды можно временно «переключать» реализацию, чтобы сравнить читаемость:

#include <iostream>
#include <string>

void run_reverse_command() {
    std::string s;
    std::getline(std::cin, s);

    const bool use_recursion = true; // учебный флажок

    if (use_recursion) {
        print_reverse_rec(s, 0);
    } else {
        print_reverse_loop(s);
    }

    std::cout << '\n';
}

Заметьте, что мы не смешиваем всю логику в одной функции. В реальном коде это экономит нервы: main остаётся «дирижёром», а не «оркестром, который играет сам на себе».

Мини-схема: что происходит при рекурсивной печати наоборот

Иногда полезно буквально увидеть порядок: сначала углубление, потом возврат. Это не обязательно для решения, но очень полезно для «внутреннего дебаггера в голове».

flowchart TD
    A["print_reverse_rec(i=0)"] --> B["print_reverse_rec(i=1)"]
    B --> C["print_reverse_rec(i=2)"]
    C --> D["print_reverse_rec(i=3)"]
    D --> E["i==size -> return"]
    E --> D2["печать s[2]"]
    D2 --> C2["печать s[1]"]
    C2 --> B2["печать s[0]"]

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

7. Типичные ошибки

Ошибка №1: перепутать «что соответствует базе» и инициализировать накопитель неверно.
В рекурсии вы возвращаете правильное значение в базовом случае (0 для суммы, 1 для произведения). В цикле это превращается в начальное значение переменной-накопителя. Если вы по привычке ставите 0 везде, факториал станет всегда равен нулю, и вы получите идеальную модель «как быстро уничтожить любую математику».

Ошибка №2: потерять порядок действий при переводе рекурсии в цикл.
Если в рекурсии действие выполнялось на возврате (после рекурсивного вызова), то прямой «вперёд-цикл» может дать другой порядок. Для строки это особенно заметно: вместо dcba вы получите abcd. В таких случаях либо делайте обратный проход, либо честно оставляйте рекурсию, если она действительно читабельнее.

Ошибка №3: неправильные границы в цикле (off-by-one) после перевода.
Рекурсивное условие if (i == s.size()) return очень конкретное: дошли до конца — стоп. При переводе в цикл легко написать i <= s.size() и случайно залезть в s[s.size()], а это уже выход за границы строки. Лекарство простое и скучное: внимательно сопоставляйте базовый случай и границы цикла, особенно < и <=.

Ошибка №4: обратный цикл по std::size_t с «уходом ниже нуля».
Шаблон for (std::size_t i = s.size() - 1; i >= 0; --i) выглядит логично только человеку. Компилятор же знает, что size_t не бывает отрицательным, и условие i >= 0 фактически всегда истинно. В итоге цикл становится бесконечным (или почти бесконечным), и вы печатаете мусор. Безопасная форма — for (std::size_t i = s.size(); i > 0; --i) и печать s[i - 1].

Ошибка №5: делать выбор «рекурсия или цикл» по длине кода, а не по ясности.
Иногда рекурсия в 3 строки выглядит красиво, но вы сами через неделю не понимаете, где там база и почему оно не падает. Иногда цикл в 7 строк выглядит длиннее, но читабельнее. Цель — не «победить в конкурсе краткости», а написать код, который можно сопровождать без гадания на кофейной гуще.