С++ рекурсия

Рекурсия C++

В этом уроке мы узнаем о рекурсивной функции в C++ и ее работе с помощью примеров.

Функция, которая вызывает сама себя, называется рекурсивной функцией. И этот метод известен как рекурсия.

<час>

Работа рекурсии в C++

void recurse()
{
    ... .. ...
    recurse();
    ... .. ...
}

int main()
{
    ... .. ...
    recurse();
    ... .. ...
}

На рисунке ниже показано, как работает рекурсия, вызывая себя снова и снова.

<рисунок>

Рекурсия продолжается до тех пор, пока не будет выполнено какое-либо условие.

Чтобы предотвратить бесконечную рекурсию, можно использовать оператор if...else (или аналогичный подход), когда одна ветвь выполняет рекурсивный вызов, а другая нет.

<час>

Пример 1. Факториал числа с использованием рекурсии

// Factorial of n = 1*2*3*...*n

#include <iostream>
using namespace std;

int factorial(int);

int main() {
    int n, result;

    cout << "Enter a non-negative number: ";
    cin >> n;

    result = factorial(n);
    cout << "Factorial of " << n << " = " << result;
    return 0;
}

int factorial(int n) {
    if (n > 1) {
        return n * factorial(n - 1);
    } else {
        return 1;
    }
}

Вывод

Enter a non-negative number: 4
Factorial of 4 = 24

<час>

Работа программы Факториал

<рисунок>

Как мы видим, factorial() функция вызывает сама себя. Однако при каждом вызове мы уменьшали значение n по 1 . Когда n меньше 1 , factorial() функция в конечном итоге возвращает результат.

<час>

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

Ниже приведены плюсы и минусы использования рекурсии в C++.

<час>

Преимущества рекурсии C++

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

<час>

Недостатки рекурсии C++

• Это занимает много места в стеке по сравнению с итеративной программой.
• Он использует больше процессорного времени.
• Отладка может быть более сложной по сравнению с эквивалентной итеративной программой.