C Academy · Урок

Рекурсия и итерация

Узнайте, когда выбирать каждый подход.

«Рекурсия и итерация» — бесплатный урок C Academy на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения C Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс C Academy содержит 4 уроков всего.

Два способа повторения

Многие задачи можно решить как с помощью рекурсии, так и с помощью итерации. Итерация использует циклы, а рекурсия — вызовы функций.

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

Факториал с циклом

Вот итеративная реализация факториала с циклом. Ни одна функция не вызывает саму себя; одна переменная накапливает произведение.

#include <stdio.h>

long factorial(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++)
        result *= i;
    return result;
}

int main(void) {
    printf("%ld\n", factorial(6));
    return 0;
}

Факториал с рекурсией

Рекурсивная версия короче и напрямую отражает математическое определение.

Обе версии дают 720 при вычислении факториала 6, но используют разные механизмы.

long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Различия в использовании памяти

Итерация обычно использует небольшой фиксированный объём памяти: всего несколько локальных переменных.

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

Различия в скорости

Каждый рекурсивный вызов требует небольших затрат: нужно создать кадр и вернуться из него.

Для простых задач подсчёта циклы часто немного быстрее, потому что не создают накладных расходов на вызовы.

Когда рекурсия выигрывает

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

В таких случаях рекурсивный код короче и понятнее, чем эквивалентный цикл с ручным стеком.

Когда выигрывает итерация

Для простой линейной обработки, например суммирования массива или подсчёта, цикл проще и использует постоянный объём памяти.

Кроме того, он исключает риск переполнения стека на больших входных данных.

int sum_array(int a[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++)
        total += a[i];
    return total;
}

Одна задача, два стиля

Сумму чисел от 1 до n можно вычислить обоими способами. Ниже приведена итеративная версия, возвращающая тот же результат, что и рекурсия.

#include <stdio.h>

int sum_to(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++)
        total += i;
    return total;
}

int main(void) {
    printf("%d\n", sum_to(100));
    return 0;
}

Преобразование рекурсии в цикл

Любую рекурсию можно переписать с использованием итерации, иногда применяя собственный явный стек.

Простая линейная рекурсия, например для факториала или суммы, преобразуется в обычный цикл с переменной-аккумулятором.

#include <stdio.h>

int main(void) {
    int n = 5, result = 1;
    while (n > 1) { result *= n; n--; }
    printf("%d\n", result);
    return 0;
}

Примечание о хвостовой рекурсии

Хвостовой рекурсивный вызов является последним действием функции. Некоторые компиляторы оптимизируют его до цикла, повторно используя один кадр.

C этого не гарантирует, поэтому не полагайтесь на такую оптимизацию при глубокой рекурсии.

int sum_tail(int n, int acc) {
    if (n == 0) return acc;
    return sum_tail(n - 1, acc + n);
}

Выбор подхода

Спросите себя: является ли задача по своей природе вложенной или относится к принципу «разделяй и властвуй»? Тогда подойдёт рекурсия.

Является ли это простым линейным повторением с потенциально огромными входными данными? Тогда итерация безопаснее и часто быстрее.

Быстрая проверка

Сравните два подхода.

Итоги

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

Часто задаваемые вопросы

Урок «Рекурсия и итерация» бесплатный?

Да — полный текст урока «Рекурсия и итерация» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс C Academy, подпишись на CoddyKit PRO. Курс C Academy содержит 4 уроков всего.

Чему я научусь в уроке «Рекурсия и итерация»?

Узнайте, когда выбирать каждый подход. Ты практикуешь C Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать C Academy?

Предыдущий опыт не требуется. C Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.

Сколько времени занимает урок «Рекурсия и итерация»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке C Academy?

Да. Каждый урок C Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

← Назад к C Academy