Рекурсия

C++

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

Факториал: рекурсивная реализация

Для вычисления факториала числа используется факт 0! = 1 и рекуррентное соотношение n! = n * (n - 1)!.

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

Факториал: нерекурсивная реализация

Для сравнения, та же функция через цикл:

int factorial(int n) {
    int ans = 1;
    for (int i = 1; i <= n; ++i) {
        ans *= i;
    }
    return ans;
}

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

Вывод чисел от 1 до n без циклов

void rec(int now, int n) {
    if (now > n) {
        return;
    }
    cout << now << " ";
    rec(now + 1, n);
}

Вывод чисел от n до 1 без циклов

Если поменять местами последние две команды, получим обратный порядок:

void rec(int now, int n) {
    if (now > n) {
        return;
    }
    rec(now + 1, n);
    cout << now << " ";
}

Быстрое возведение в степень

Рассмотрим задачу возведения числа a в степень n. Наивный способ использует n - 1 умножений, но есть более быстрый рекурсивный подход.

Используем формулы:

• a^n = (a^(n / 2))^2, если n четно
• a^n = a * a^(n - 1), если n нечетно

Рекурсивная функция:

int power(int a, int n) {
    if (n == 0) {
        return 1;
    }
    if (n % 2 == 0) {
        int temp = power(a, n / 2);
        return temp * temp;
    } else {
        return a * power(a, n - 1);
    }
}

Задача «Ханойская башня»

Есть три стержня 1, 2, 3. На стержне 1 находится пирамида из n дисков. Нужно перенести ее на стержень 3, используя стержень 2 как вспомогательный. За один ход можно переносить только один диск, и нельзя класть больший диск на меньший.

Функция печатает последовательность ходов в формате: a b c, где a — номер диска, b — откуда снимаем, c — куда кладем.

Идея рекурсии для переноса n дисков со стержня f на стержень t:

• перенести n - 1 дисков с f на промежуточный v = 6 - f - t
• перенести диск n с f на t
• перенести n - 1 дисков с v на t

void hanoi(int n, int f, int t) {
    if (n == 0) {
        return;
    }
    int v = 6 - f - t;
    hanoi(n - 1, f, v);
    cout << n << " " << f << " " << t << endl;
    hanoi(n - 1, v, t);
}