§15 Рекурсия

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

У нас на обед — салат «Рекурсивный» : помидоры, огурцы, салат.DaGGeR

Рекурсивная функция — это функция которая вызывает сама себя напрямую или косвенно (через другие функции).
Рекурсивный вариант реализации алгоритма обычно выглядит изящнее, делает текст программы более компактным и понятным, но исполняется медленнее. Любой рекурсивный алгоритм может иметь нерекурсивную реализацию.
Для того, чтобы не происходило бесконечных вызовов функции, рекурсивный алгоритм содержит условие завершения рекурсии и строится по схеме, в которой рекурсивный вызов находится в одной из ветви условной инструкции.
Рассмотрим пример программы с рекурсией — вычисление факториала числа. Постановка задачи. Используя свойство n! = (n - 1)! * n реализовать в программе рекурсивную функцию вычисления n!
Программа 15.1a

#include <iostream>
using namespace std;
long long factor(int);

int main() {
	int n;
	cout << "n = "; cin >> n;
	cout << n << "! = " << factor(n);
	return 0;
}
long long factor(int x) {
	if (x == 1)
		return 1;
	else
		return factor(x - 1) * x;
}
n = 20
20! = 2432902008176640000

Программа 1а имеет свой нерекурсивный аналог с итерационным (циклическим) алгоритмом, который будет работать быстрее и эффективнее:
Программа 15.1b

#include <iostream>
using namespace std;

int main() {
	int n;
	long long f = 1;
	cout << "n = "; cin >> n;
	for (int i = 1; i <= n; i++)
		f *= i;
	cout << n << "! = " << f;
	return 0;

Механизм рекурсии

В чем причины медлительности и неэффективности рекурсивных алгоритмов? Для хранения всех отложенных вызовов (с разными аргументами) рекурсивной функции, а также значений всех локальных переменных используется стек (механизм «последним пришел — первым ушел»). (Учебник п. 61 стр. 32). При выполнении операций в стеке расходуется время и заполняется память. Если отложенных вызовов будет слишком много — память будет переполнена и программа завершится с ошибкой.
Чтобы яснее представить как выполняется рекурсивный алгоритм решим более наглядную задачу. Вывести числовой ряд от 0 до N. Реализацию задачи выполнить с помощью рекурсивной функции.
Программа 15.2

#include <iostream>
using namespace std;
void typeNumber(int);

int main() {
	int n;
	cout << "n = "; cin >> n;
	typeNumber(n);
	return 0;
}
void typeNumber(int x) {
	if (x < 0)
		return;
	else
		typeNumber(x - 1);
	cout << x << " ";
}
n = 10
0 1 2 3 4 5 6 7 8 9 10 

Рекурсивный вызов функции typeNumber можно представить с помощью схемы:
recurs2
Стек постепенно будет заполняться данными от каждого отложенного рекурсивного вызова: параметры, локальные переменные и точка возврата до тех пор, пока условие будет истинно. Максимальный набор блоков памяти в стеке от вызовов данной функции называют глубиной рекурсии. После вызова функции typeNumber в последний раз — весь процесс возвращается вспять: функция typeNumber(0) завершает свою работу, печатает результат (0) и возвращает управление функции вызвавшей её (typeNumber(1)) и т. д., пока не произойдет возврат функции инициировавшей рекурсию (typeNumber(3)).
Рассмотрим еще одну задачу в которой в функцию будут передаваться два аргумента, но только один из них будет изменяться с каждым шагом рекурсии.
Постановка задачи. Составить программу возведения a в степень b, где a и b целые числа (> 0) в виде рекурсивного алгоритма.
Программа 15.3

#include <iostream>
using namespace std;
int myPow(int, int);

int main() {
	int a, b;
	cout << "a = "; cin >> a;
	cout << "b = "; cin >> b;
	cout << myPow(a, b);
	return 0;
}
int myPow(int x, int y) {
	if (y == 0) 
		return 1;
	else
		return myPow(x, y-1) * x;
}
a = 5
b = 10
9765625

Одним из лучших примеров использования рекурсивного алгоритма является метод расчета наибольшего общего делителя (НОД) для двух целых чисел, на основании следующего свойства: НОД(a, b) = НОД(a - b, b), при a >= b (алгоритм Евклида). В программе 4 реализован алгоритм нахождения НОД(a, b), но задача решается не путем вычитания, а получения остатка отделения a % b, что позволит существенно сократить количество рекурсивных вызовов.
Программа 15.4

#include <iostream>
using namespace std;
int nod(int, int);

int main() {
	int a, b;
	cout << "a = "; cin >> a;
	cout << "b = "; cin >> b;
	cout << "NOD(" << a << ", " << b << ") = " << nod(a, b);
	return 0;
}
int nod(int x, int y) {
	if (x % y == 0)
		return y;
	else
		return nod(y, x % y);
}
a = 171
b = 36
NOD(171, 36) = 9

Фракталы

К сожалению, C++ не обладает собственной стандартной графической библиотекой («сапожник без сапог»). Поэтому мы посмотрим использование рекурсии на примере программы в среде программирования Python с помощью библиотечного модуля Turtle. Составим программу рисования «квадратной» спирали. В этой программе вызов функции drawSpiral — рекурсивный.
Программа 15.5

from turtle import*
myTurtle = Turtle()
myWin = Screen()
myTurtle.pensize(3)
myTurtle.hideturtle()
myTurtle.speed(10)
myTurtle.penup()
myTurtle.goto(-150, 150)
myTurtle.pendown()

def drawSpiral(myTurtle, lineLen):
    if lineLen > 0:
        myTurtle.forward(lineLen)
        myTurtle.right(90)
        drawSpiral(myTurtle,lineLen - 10)

drawSpiral(myTurtle,300)
myWin.exitonclick()

spiro
Наиболее интересное применение рекурсии в графических приложениях — создание фракталов. Фракта́лами (от лат. fractus — дроблёный, сломанный, разбитый) называют геометрические фигуры, обладающие свойством самоподобия, то есть состоящие из частей, подобных всей фигуре. Программы, использующие модуль Turtle для рисования самых известных фракталов, можно посмотреть на страничке сайта в разделе программирования на Python. Ниже показаны как выглядят два известных фрактала — фрактал Коха (сверху) и Множество Мандельброта (снизу, полученное с помощью программы Gnofract 4D).
koh
mandelbrot

Вопросы

п. 61 стр. 33

Домашнее задание

1. Описать рекурсивную функцию DigitSum(K) целого типа, которая находит сумму и произведение цифр целого числа K, не используя оператор цикла. С помощью этой функции найти суммы и произведения цифр для пяти данных целых чисел.
2. Описать рекурсивную функцию Fib1(N) целого типа, вычисляющую N-й элемент последовательности чисел Фибоначчи (N — целое число): F1 = F2 = 1, FK = FK–2 + FK–1, K = 3, 4, ... .
С помощью этой функции найти пять чисел Фибоначчи с данными номерами, и вывести эти числа вместе с количеством рекурсивных вызовов функции Fib1, потребовавшихся для их нахождения. (Рекурсивный алгоритм вычисления чисел Фибоначчи является очень плохим примером использования рекурсии. Объясните почему? Ответ можно найти здесь)

Большая наука. Великое в малом. Фракталы

Ссылки

Рекурсия

Литература
  1. Прата, Стивен. Язык программирования C++. Лекции и упражнения, 6-е изд.: Пер. с англ. — М.: ООО «И.Д. Вильяме», 2012
  2. Липпман Б. Стенли, Жози Лажойе, Барбара Э. Му. Язык программирования С++. Базовый курс. Изд. 5-е. М: ООО «И. Д. Вильямс», 2014
  3. Эллайн А. C++. От ламера до программера. СПб.: Питер, 2015
  4. Джосаттис Н. М. Стандартная библиотека C++: справочное руководство, 2-е изд.-М.: Вильямс, 2014


Добавить комментарий