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)
        // sum() function calls itself
        return n + sum(n-1); 
    else
        return n;
}

Вывод

Enter a positive integer:3
sum = 6

<час>

Первоначально sum() вызывается из main() функция с числом передается как аргумент.

Предположим, значение n внутри sum() изначально 3. Во время следующего вызова функции 2 передается в sum() функция. Этот процесс продолжается до тех пор, пока n равно 0.

Когда n равно 0, if условие не выполняется, и else часть выполняется, возвращая сумму целых чисел в конечном итоге в main() функция.

<рисунок> <час>

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

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

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