Рекурсия в C

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

В этом уроке Вы узнаете:

• Что такое рекурсия и как она работает.
• Как реализовывать рекурсивные функции.
• Чем рекурсия отличается от итерации.

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

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

Пример синтаксиса:

void function() { function(); // Recursive call }

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

Пример: рекурсия

Эта программа демонстрирует рекурсию, выводя числа от 5 до 1.

#include <stdio.h>

void countDown(int n) {
    if (n <= 0) return; // Base case
    printf("%d\n", n);
    countDown(n - 1); // Recursive call
}

int main() {
    countDown(5);
    return 0;
}

Базовый случай в рекурсии

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

Пример:

if (n == 0) return;

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

Пример: вычисление факториала с помощью рекурсии

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

#include <stdio.h>

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

int main() {
    printf("Factorial of 5: %d\n", factorial(5));
    return 0;
}

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

Рекурсия и итерация (циклы) могут давать одинаковые результаты, но работают по-разному.

Различия:

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

Пример: последовательность Фибоначчи (рекурсивная)

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

#include <stdio.h>

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

int main() {
    printf("Fibonacci(5): %d\n", fibonacci(5));
    return 0;
}

Когда следует использовать рекурсию?

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

• Обходом деревьев.
• Поиском с возвратом (например, при решении лабиринтов).
• Математическими задачами, такими как вычисление факториала и последовательности Фибоначчи.

Итоги

В этом уроке Вы узнали:

• Что такое рекурсия и как она работает.
• О важности базового случая.
• О различии между рекурсией и итерацией.

Далее мы рассмотрим массивы и строки в C!