Статья Автор: Лебедев Дмитрий

Конспект 13. Рекурсия


C++_Рекурсия. Часть 1

Рекурсия — это метод реализации функции, при котором функция вызывает сама себя, но с другими значениями параметров. Рассмотрим пример рекурсивной функции, которая вычисляет факториал числа n!=1⋅2⋅…⋅n. Для вычисления факториала числа наша функция будет использовать тот факт, что 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 << " ";
}

C++_Рекурсия Часть 2

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

Рассмотрим задачу о возведении числа a в степень n. Конечно, можно написать функцию, которая использует n−1 умножение для нахождения числа an, но это не самый быстрый способ. Чтобы ускорить процесс, воспользуемся следующими рекуррентными формулами:

an=(an/2)2, если nn чётно;

an=a⋅an−1, если nn нечётно.

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

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);
    }
}

C++_Рекурсия. Часть 3

«Ханойская башня» является одной из популярных головоломок XIX века. Даны три стержня, пронумерованные числами 1, 2, 3. На стержень 1 надета пирамидка из n дисков различного диаметра в порядке возрастания диаметра дисков, если рассматривать их сверху вниз. Диски можно перекладывать с одного стержня на другой по одному, при этом диск нельзя класть на диск меньшего диаметра. Необходимо переложить всю пирамидку со стержня 1 на стержень 3, используя стержень 2 как вспомогательный, за минимальное число перекладываний.

Требуется написать функцию, которая решает головоломку: для данного числа дисков n печатает последовательность перекладываний в формате a b c, где a — номер перекладываемого диска, b — номер стержня, с которого снимается данный диск, c — номер стержня, на который надевается данный диск.

dra

Для решения этой задачи напишем рекурсивную функцию, которая будет получать размер пирамидки, номер стержня, на который она надета, и номер стержня, на который она должна переместиться. Тогда, чтобы переместить пирамидку размером 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);
}

Задачи для тренировки

1) ?А?

  
2) Разворот последовательности  
3) Функция Аккермана  
4) Быстрое возведение в степень  
5) Ханойские башни  
6) Рекурсивный перевод  
7) Лесенки  


Печать