Рекурсия в C: простое руководство по написанию и использованию рекурсивных функций

Рекурсия в C: простое руководство

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

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

---

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

void recurse() {
    /* пред-обработка */
    recurse();
    /* пост-обработка */
}
int main() {
    /* начальная настройка */
    recurse();
    /* завершающие действия */
}

Рекурсия повторяется до достижения условия остановки — часто называемого базовым случаем. Использование if…else или аналогичной конструкции гарантирует, что функция в конечном итоге завершится и избежит бесконечного цикла.

---

Пример: Сумма натуральных чисел через рекурсию

#include <stdio.h>
int sum(int n);
int main() {
    int number, result;
    printf("Enter a positive integer: ");
    scanf("%d", &number);
    result = sum(number);
    printf("sum = %d", result);
    return 0;
}
int sum(int n) {
    if (n != 0)
        return n + sum(n - 1); // Рекурсивный вызов
    else
        return 0; // Базовый случай
}

Вывод

Enter a positive integer: 3
sum = 6

---

В этом примере sum() вызывается из main() с пользовательским вводом. Функция вызывает себя с уменьшенным n до достижения нуля. Тогда базовый случай возвращает 0, и рекурсивные вызовы разворачиваются, складывая каждое промежуточное значение обратно в main().

---

Преимущества и недостатки рекурсии

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

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

Классические примеры рекурсии

Факториал

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

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

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

Примечание: наивная рекурсия для Фибоначчи экспоненциальна O(2^n). Используйте мемоизацию или итеративный подход для эффективности.

Обход дерева (инфиксный)

void inorder(TreeNode* node) {
    if (!node) return;
    inorder(node->left);
    printf("%d ", node->val);
    inorder(node->right);
}

Хвостовая рекурсия (Tail Recursion)

Если рекурсивный вызов — последнее действие функции, компилятор может оптимизировать её в итерацию (TCO — Tail Call Optimization), не расходуя стек:

// Хвостовая рекурсия для суммы
int sum_tail(int n, int acc) {
    if (n == 0) return acc;
    return sum_tail(n - 1, acc + n);
}
// Вызов: sum_tail(n, 0);