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

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

Возьмём классический пример — факториал — и напишем оба варианта рядом:

// Итеративно
static int FactorialLoop(int n)
{
    int result = 1;
    for (int i = 2; i <= n; i++)
        result *= i;
    return result;
}

// Рекурсивно
static int FactorialRecursive(int n)
{
    if (n == 0) return 1;
    return n * FactorialRecursive(n - 1);
}

Оба дают одинаковый результат. Итеративная версия чуть длиннее, зато работает с любым n — стек не переполнится. Рекурсивная красивее и напрямую отражает математическое определение: n! = n × (n−1)!

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

Представьте, что вам нужно обойти дерево папок на диске — найти все файлы внутри, включая вложенные папки и папки внутри папок. Итеративно это будет выглядеть примерно так:

static void ListFilesIterative(string path)
{
    var stack = new Stack<string>();
    stack.Push(path);

    while (stack.Count > 0)
    {
        string current = stack.Pop();
        foreach (string file in Directory.GetFiles(current))
            Console.WriteLine(file);
        foreach (string dir in Directory.GetDirectories(current))
            stack.Push(dir);
    }
}

Работает. Но заметьте: чтобы организовать обход дерева итеративно, нам пришлось вручную создать Stack<string> и управлять им. Мы сами имитируем стек вызовов.

А вот рекурсивная версия:

static void ListFilesRecursive(string path)
{
    foreach (string file in Directory.GetFiles(path))
        Console.WriteLine(file);

    foreach (string dir in Directory.GetDirectories(path))
        ListFilesRecursive(dir);  // просто вызываем себя для каждой папки
}

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

Другие задачи, где рекурсия естественна: обход деревьев (бинарное дерево поиска, дерево выражений), разбор вложенных структур (JSON, XML, HTML), алгоритмы «разделяй и властвуй» (быстрая сортировка, merge sort — которые мы уже видели), поиск в глубину (DFS) в графах. Во всех этих случаях данные сами имеют рекурсивную природу: папка может содержать папки, узел дерева содержит дочерние узлы, элемент JSON может содержать другие элементы JSON. Когда данные рекурсивны — код тоже должен быть рекурсивным. Это не прихоть, а следствие правильного моделирования задачи. Где итерация выигрывает — линейные задачи и вопросы производительности.

Для задач, которые линейно идут от начала к концу — цикл проще, понятнее и быстрее. Например, сумма элементов массива:

// Итеративно — просто и понятно
static int SumArray(int[] arr)
{
    int sum = 0;
    foreach (int x in arr)
        sum += x;
    return sum;
}

// Рекурсивно — зачем?
static int SumArrayRecursive(int[] arr, int index)
{
    if (index == arr.Length) return 0;
    return arr[index] + SumArrayRecursive(arr, index + 1);
}

Рекурсивная версия сложнее для чтения и потребует отдельный параметр index. При массиве из 100 000 элементов — 100 000 фреймов в стеке. Это реальный риск StackOverflowException.

Ещё один минус рекурсии — накладные расходы. Каждый вызов функции требует: создания фрейма в стеке, копирования параметров, записи адреса возврата, восстановления этих данных при возврате. Для простых задач всё это лишняя работа. Цикл работает быстрее — никаких фреймов, только счётчик и переменные в регистрах процессора. Для массива из миллиона элементов разница ощутима.

Вот таблица для сравнения. Сумма массива из 1 000 000 элементов: итеративная версия — несколько миллисекунд. Рекурсивная — скорее всего даже не запустится: 1 000 000 фреймов стека это гарантированный StackOverflowException. Это не теоретическая проблема — это практическое ограничение.

Числа Фибоначчи — ещё один классический пример, где наивная рекурсия ужасна:

// Наивная рекурсия — катастрофа
static int FibSlow(int n)
{
    if (n <= 1) return n;
    return FibSlow(n - 1) + FibSlow(n - 2);
}

// FibSlow(40) = ~100 млн вызовов функции!
// FibSlow(50) = ~10 триллионов вызовов

Проблема в том, что FibSlow(40) вычисляет FibSlow(30) несколько раз, FibSlow(20) — много раз, FibSlow(10) — огромное количество раз. Одни и те же значения пересчитываются снова и снова. Сложность — O(2ⁿ). При n=50 программа будет работать часами.

Итеративная версия:

static int FibFast(int n)
{
    if (n <= 1) return n;
    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++)
    {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

// FibFast(1000) вычисляется мгновенно

Сложность O(n), никаких дублирующих вычислений. Вот вам наглядный пример: рекурсия может быть не просто медленнее, а экспоненциально медленнее, если структура задачи не подходит.

Итого: как выбирать?

Спросите себя: является ли структура данных или задача рекурсивной по природе? Если вы работаете с деревьями, графами, вложенными структурами — рекурсия, скорее всего, даст более чистый код. Если задача линейная (пройти массив, посчитать сумму, найти максимум) — итерация проще и безопаснее.

Спросите себя: насколько глубокой потенциально может быть рекурсия? Если глубина ограничена (дерево папок обычно не глубже 20 уровней), рекурсия безопасна. Если глубина зависит от входных данных и может быть большой (рекурсия по массиву из миллиона элементов) — лучше итерация.

Спросите себя: не вычисляются ли одни и те же значения повторно? Если да — наивная рекурсия будет медленной, и нужна мемоизация или итеративный подход.

Рекурсия — инструмент. Как молоток: отличная вещь для гвоздей, плохая — для шурупов. Знание того, когда применять каждый подход, — признак опытного разработчика. Подкрепим теорию ещё одним конкретным примером — подсчёт цифр числа. Сколько цифр в числе 4823? Четыре. Задача простая, но поучительная.

Итеративный вариант прямолинеен: делим число на 10, пока оно не станет нулём, считаем шаги.

static int CountDigitsLoop(int n)
{
    if (n == 0) return 1;
    int count = 0;
    while (n > 0)
    {
        n /= 10;
        count++;
    }
    return count;
}

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

static int CountDigitsRecursive(int n)
{
    if (n < 10) return 1;
    return 1 + CountDigitsRecursive(n / 10);
}

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

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

class Comment
{
    public string Text { get; set; }
    public List<Comment> Replies { get; set; } = new List<Comment>();
}

static void PrintAllComments(Comment comment, int depth = 0)
{
    Console.WriteLine(new string(' ', depth * 2) + comment.Text);
    foreach (var reply in comment.Replies)
        PrintAllComments(reply, depth + 1);
}

Это типичная задача обхода дерева. Каждый комментарий может иметь произвольное количество ответов, каждый ответ — свои ответы, и так до любой глубины. Итеративно это решается через явный стек — но код становится значительно сложнее и менее читаемым. Рекурсивная версия буквально говорит: «напечатай текущий комментарий, потом рекурсивно обработай каждый ответ» — и это идеально соответствует структуре данных.

Именно в таких случаях рекурсия не просто удобна — она является правильным инструментом. Код выражает логику задачи напрямую, без искусственных преобразований.

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

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

Итерация — повторение с помощью цикла (for, while). Состояние хранится в переменных, не создаёт накладных расходов на стек.

Рекурсия — повторение через самовызов функции. Состояние хранится в параметрах и стеке вызовов. Элегантна для задач с рекурсивной структурой данных.

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

Итерация выигрывает: линейные задачи, большие входные данные (риск переполнения стека), задачи с повторными вычислениями одних значений.

Сигнал выбрать рекурсию: вы вынуждены вручную создавать Stack<T> для итеративного решения — значит, рекурсия сделает это за вас автоматически.

Наивная рекурсия для чисел Фибоначчи — классический антипаттерн: O(2ⁿ) из-за повторных вычислений. Итеративная версия работает за O(n).