C Academy · Урок

Как работает рекурсия

Базовые случаи и стек вызовов.

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

Что такое рекурсия

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

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

Базовый случай

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

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

int countdown(int n) {
    if (n == 0) return 0; /* base case */
    return countdown(n - 1);
}

Рекурсивный случай

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

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

int sum_to(int n) {
    if (n == 0) return 0;       /* base case */
    return n + sum_to(n - 1);   /* recursive case */
}

Первая полноценная программа

Давайте запустим полную программу, которая с помощью рекурсии суммирует числа от 1 до 5.

Результат должен быть равен 15.

#include <stdio.h>

int sum_to(int n) {
    if (n == 0) return 0;
    return n + sum_to(n - 1);
}

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

Трассировка вызовов

Рекурсию полезно прослеживать вручную. Для sum_to(3):

sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0

Затем вызовы возвращаются обратно: 1, затем 3, затем 6.

Стек вызовов

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

При углублении рекурсии кадры накапливаются. Когда вызов возвращается, его кадр удаляется, а управление передаётся обратно вызывающей функции.

Разворачивание и сворачивание

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

Сворачивание начинается, когда базовый случай возвращает результат и каждый вызов завершает свою работу, используя возвращённое значение.

#include <stdio.h>

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

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

Возвращаемые значения передаются обратно

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

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

int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

Вывод во время рекурсии

Вы можете выводить значение до или после рекурсивного вызова. Вывод до вызова показывает числа при углублении, а вывод после — при возвращении обратно.

#include <stdio.h>

void down(int n) {
    if (n == 0) return;
    printf("%d ", n);
    down(n - 1);
}

int main(void) {
    down(5);
    printf("\n");
    return 0;
}

Вывод при возвращении

Переместите printf после рекурсивного вызова, и порядок изменится на обратный. Сначала будет выведен результат самого глубокого вызова.

Вместо 5 4 3 2 1 программа выведет 1 2 3 4 5.

#include <stdio.h>

void up(int n) {
    if (n == 0) return;
    up(n - 1);
    printf("%d ", n);
}

int main(void) {
    up(5);
    printf("\n");
    return 0;
}

Два правила, которые нужно помнить

Правильная рекурсивная функция соблюдает два правила:

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

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

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

Проверьте, насколько хорошо Вы поняли основы рекурсии.

Повторение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

← Назад к C Academy