C Academy · Урок

Классические задачи на рекурсию

Факториал и числа Фибоначчи.

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

Классические задачи

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

В этом уроке мы рассмотрим факториал, числа Фибоначчи, сумму цифр, наибольший общий делитель и вывод в обратном порядке.

Факториал

Факториал числа n — это n, умноженное на факториал числа n минус 1, причём 1! равно 1.

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

#include <stdio.h>

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

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

Числа Фибоначчи

Каждое число Фибоначчи равно сумме двух предыдущих. Для рекурсивного определения нужны два базовых случая: fib(0)=0 и fib(1)=1.

На каждом шаге эта версия выполняет два вызова.

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

Вычисление чисел Фибоначчи

Вот полная программа. Она должна вывести 55 для fib(10).

Обратите внимание: эта наивная версия повторяет вычисления, поэтому медленно работает при больших значениях n.

#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

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

Сумма цифр

Чтобы сложить цифры числа, получите последнюю цифру с помощью n % 10, а для оставшейся части выполните рекурсивный вызов с n / 10.

Базовый случай наступает, когда n достигает 0.

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}

Сумма цифр в действии

Для 1234 сумма равна 1+2+3+4 = 10. Давайте проверим это с помощью полной программы.

#include <stdio.h>

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}

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

Наибольший общий делитель

Алгоритм Евклида естественным образом реализуется рекурсивно. GCD чисел a и b равен GCD чисел b и a % b.

Когда b становится равным 0, ответом является a.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Полная программа для GCD

GCD чисел 48 и 18 равен 6. Эта программа выводит это значение.

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main(void) {
    printf("%d\n", gcd(48, 18));
    return 0;
}

Переворачивание числа

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

Эта вспомогательная функция с помощью рекурсии выводит каждую цифру числа на отдельной строке.

#include <stdio.h>

void print_digits(int n) {
    if (n == 0) return;
    print_digits(n / 10);
    printf("%d ", n % 10);
}

int main(void) {
    print_digits(729);
    printf("\n");
    return 0;
}

Возведение в степень

Возведение основания в степень тоже задаётся рекурсивно: основание^показатель равно основанию, умноженному на основание^(показатель-1).

Базовый случай — показатель 0, при котором возвращается 1.

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

Шаблоны, которые Вы будете использовать снова

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

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

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

Выберите правильные базовые случаи.

Итоги

Факториал, числа Фибоначчи, сумма цифр, GCD и возведение в степень используют один рекурсивный шаблон: обработайте базовый случай, затем объедините текущее значение с меньшей подзадачей.

Эти заготовки подходят и для многих других задач.

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

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

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

Чему я научусь в уроке «Классические задачи на рекурсию»?

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

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

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

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

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

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

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

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

← Назад к C Academy