Рекурсия в C: основы, примеры и условия выхода

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

void recursion() {
    recursion();  // бесконечный вызов себя
}
int main() {
    recursion();
}

Факториал числа

Классический пример рекурсии — вычисление факториала:

#include <stdio.h>

unsigned long long factorial(unsigned int n) {
    if (n <= 1) return 1;          // базовый случай
    return n * factorial(n - 1);   // рекурсивный шаг
}

int main() {
    int i = 12;
    printf("Factorial of %d is %llu\n", i, factorial(i));
    return 0;
}

Результат:

Factorial of 12 is 479001600

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

Ещё один классический пример — рекурсивное вычисление чисел Фибоначчи:

#include <stdio.h>

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

int main() {
    for (int i = 0; i < 10; i++) {
        printf("%d\n", fibonacci(i));
    }
    return 0;
}

Результат:

0
1
1
2
3
5
8
13
21
34

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

Лучшие практики рекурсии

• Всегда определяйте чёткий базовый случай.
• Убедитесь, что каждый рекурсивный вызов приближает к базовому случаю.
• Оцените глубину рекурсии — стек ограничен (обычно ~1–8 МБ).
• Для глубокой рекурсии рассмотрите итеративные альтернативы или хвостовую рекурсию (если компилятор её оптимизирует).
• Используйте static или глобальные переменные с осторожностью — они делают функцию нереентерабельной.