Освоение рекурсии в C++: концепции, примеры и лучшие практики

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

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

Функция, вызывающая саму себя, называется рекурсивной. Этот мощный метод известен как рекурсия.

---

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

void recurse()
{
    // код до рекурсии
    recurse(); // рекурсивный вызов
    // код после рекурсии
}

int main()
{
    // код настройки
    recurse();
    // код завершения
}

На рисунке ниже показана повторяющаяся природа самовызова рекурсии.

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

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

---

Пример 1: вычисление факториала рекурсивно

// Вычисляет n! = 1 × 2 × … × 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 на единицу. Когда n становится меньше или равно 1, функция возвращает 1, и рекурсия разворачивается, выдавая окончательный результат.

---

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

Ниже приведены ключевые преимущества и недостатки рекурсии.

---

Преимущества

• Приводит к лаконичному, выразительному коду.
• Необходима для естественных решений задач, связанных с деревьями, графами и комбинаторным поиском.

---

Недостатки

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

---

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