Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Самый простой вариант увидеть рекурсию – это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.

В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия – определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию). Типичными рекурсивными задачами являются задачи: нахождения n!, числа Фибоначчи. Такие задачи мы уже решали, но с использованием циклов, то есть итеративно. Вообще говоря, всё то, что решается итеративно можно решить рекурсивно, то есть с использованием рекурсивной функции. Всё решение сводится к решению основного или, как ещё его называют, базового случая. Существует такое понятие как шаг рекурсии или рекурсивный вызов. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение. Разработаем программу, в которой объявлена рекурсивная функция, вычисляющая n!

"stdafx.h" #include << "Enter n!: "; cin >> n; cout << n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

// код Code::Blocks

// код Dev-C++

// factorial.cpp: определяет точку входа для консольного приложения. #include using namespace std; unsigned long int factorial(unsigned long int);// прототип рекурсивной функции int i = 1; // инициализация глобальной переменной для подсчёта кол-ва рекурсивных вызовов unsigned long int result; // глобальная переменная для хранения возвращаемого результата рекурсивной функцией int main(int argc, char* argv) { int n; // локальная переменная для передачи введенного числа с клавиатуры cout << "Enter n!: "; cin >> n; cout << n << "!" << "=" << factorial(n) << endl; // вызов рекурсивной функции return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 cout << "Step\t" << i << endl; i++; // операция инкремента шага рекурсивных вызовов cout << "Result= " << result << endl; result = f * factorial(f - 1); // функция вызывает саму себя, причём её аргумент уже на 1 меньше return result; }

В строках 7, 9, 21 объявлен тип данных unsigned long int , так как значение факториала возрастает очень быстро, например уже 10! = 3 628 800. Если не хватит размера типа данных, то в результате мы получим совсем не правильное значение. В коде объявлено больше операторов, чем нужно, для нахождения n!. Это сделано для того, чтобы, отработав, программа показала, что происходит на каждом шаге рекурсивных вызовов. Обратите внимание на выделенные строки кода, строки 23, 24, 28 — это рекурсивное решение n!. Строки 23, 24 являются базовым решением рекурсивной функции, то есть, как только значение в переменной f будет равно 1 или 0 (так как мы знаем, что 1! = 1 и 0! = 1), прекратятся рекурсивные вызовы, и начнут возвращаться значения, для каждого рекурсивного вызова. Когда вернётся значение для первого рекурсивного вызова, программа вернёт значение вычисляемого факториала. В строке 28 функция factorial() вызывает саму себя, но уже её аргумент на единицу меньше. Аргумент каждый раз уменьшается, чтобы достичь частного решения. Результат работы программы (см. Рисунок 1).

Enter n!: 5 Step 1 Result= 0 Step 2 Result= 0 Step 3 Result= 0 Step 4 Result= 0 5!=120

Рисунок 1 — Рекурсия в С++

По результату работы программы хорошо виден каждый шаг и результат на каждом шаге равен нулю, кроме последнего рекурсивного обращения. Необходимо было вычислить пять факториал. Программа сделала четыре рекурсивных обращения, на пятом обращении был найден базовый случай. И как только программа получила решение базового случая, она порешала предыдущие шаги и вывела общий результат. На рисунке 1 видно всего четыре шага потому, что на пятом шаге было найдено частное решение, что в итоге вернуло конечное решение, т. е. 120. На рисунке 2 показана схема рекурсивного вычисления 5!. В схеме хорошо видно, что первый результат возвращается, когда достигнуто частное решение, но никак не сразу, после каждого рекурсивного вызова.

Рисунок 2 — Рекурсия в С++

Итак, чтобы найти 5! нужно знать 4! и умножить его на 5; 4! = 4 * 3! и так далее. Согласно схеме, изображённой на рисунке 2, вычисление сведётся к нахождению частного случая, то есть 1!, после чего по очереди будут возвращаться значения каждому рекурсивному вызову. Последний рекурсивный вызов вернёт значение 5!.

Переделаем программу нахождения факториала так, чтобы получить таблицу факториалов. Для этого объявим цикл for , в котором будем вызывать рекурсивную функцию.

using namespace std; unsigned long int factorial(unsigned long int);// прототип рекурсивной функции int i = 1; // инициализация глобальной переменной для подсчёта кол-ва рекурсивных вызовов unsigned long int result; // глобальная переменная для хранения возвращаемого результата рекурсивной функцией int main(int argc, char* argv) { int n; // локальная переменная для передачи введенного числа с клавиатуры cout << "Enter n!: "; cin >> n; for (int k = 1; k <= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } system("pause"); return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i <> n; for (int k = 1; k <= n; k++) { cout << k << "!" << "=" << factorial(k) << endl; // вызов рекурсивной функции } return 0; } unsigned long int factorial(unsigned long int f) // рекурсивная функция для нахождения n! { if (f == 1 || f == 0) // базовое или частное решение return 1; // все мы знаем, что 1!=1 и 0!=1 //cout << "Step\t"<< i < << "Enter number from the Fibonacci series: "; cin >> <= entered_number; counter++) cout << setw(2) <

// код Code::Blocks

// код Dev-C++

// fibonacci.cpp: определяет точку входа для консольного приложения. #include // библиотека для форматирования выводимой информации на экран #include using namespace std; unsigned long fibonacci(unsigned long);// прототип рекурсивной функции поиска чисел из ряда Фибоначчи int main(int argc, char* argv) { unsigned long entered_number; cout << "Enter number from the Fibonacci series: "; cin >> entered_number; for (int counter = 1; counter <= entered_number; counter++) cout << setw(2) < #include using namespace std; void tower(int, int, int, int); // объявление прототипа рекурсивной функции int count = 1; // глобальная переменная для подсчёта количества шагов int _tmain(int argc, _TCHAR* argv) { cout << "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >> number; cout << "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> basic_rod; cout << "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> final_rod; int help_rod; // блок определения номера вспомогательного стержня, анализируя номера начального и финального стержня if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(// запуск рекурсивной функции решения задачи Ханойских башен number, // переменная, хранящая количество дисков, которые надо переместить basic_rod, // переменная, хранящая номер стержня, на котором диски будут находится изначально help_rod , // переменная, хранящая номер стержня, который используется, как вспомогательный final_rod); // переменная, хранящая номер стержня, на который необходимо переместить диски system("pause"); return 0; } void tower(int count_disk, int baza, int help_baza, int new_baza) { if (count_disk == 1) // условие завершения рекурсивных вызовов { cout << setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

// код Code::Blocks

// код Dev-C++

// hanoi_tower.cpp: определяет точку входа для консольного приложения. // Программа, рекурсивно решающая задачу "Ханойская башня" #include #include using namespace std; void tower(int, int, int, int); // объявление прототипа рекурсивной функции int count = 1; // глобальная переменная для подсчёта количества шагов int main() { cout << "Enter of numbers of disks: ";// введите количество дисков, которые надо переместить int number; cin >> number; cout << "Enter the number of basic rod: "; // введите номер стержня, на котором диски будут находится изначально int basic_rod; cin >> basic_rod; cout << "Enter the number of final rod: "; // введите номер стержня, на который необходимо переместить диски int final_rod; cin >> final_rod; int help_rod; // блок определения номера вспомогательного стержня, анализируя номера начального и финального стержня if (basic_rod != 2 && final_rod != 2) help_rod = 2; else if (basic_rod != 1 && final_rod != 1) help_rod = 1; else if (basic_rod != 3 && final_rod != 3) help_rod = 3; tower(// запуск рекурсивной функции решения задачи Ханойских башен number, // переменная, хранящая количество дисков, которые надо переместить basic_rod, // переменная, хранящая номер стержня, на котором диски будут находится изначально help_rod , // переменная, хранящая номер стержня, который используется, как вспомогательный final_rod); // переменная, хранящая номер стержня, на который необходимо переместить диски return 0; } void tower(int count_disk, int baza, int help_baza, int new_baza) { if (count_disk == 1) // условие завершения рекурсивных вызовов { cout << setw(2) << count << ") "<< baza << " " << "->" << " " << new_baza << endl; count++; } else { tower(count_disk -1, baza, new_baza, help_baza); // перемещаем все диски кроме самого последнего на вспомогательный стержень tower(1, baza, help_baza, new_baza); // перемещаем последний диск с начального стержня на финальный стержень tower(count_disk -1, help_baza, baza, new_baza); // перемещаем все диски со вспомогательного стержня на финальный } }

На рисунке 5 показан пример работы рекурсивной программы Ханойская башня. Сначала мы ввели количество дисков равное трём, потом ввели базовый стержень (первый), и обозначили конечный стержень (третий). Автоматически второй стержень стал вспомогательным. Программа выдала такой результат, что он полностью совпадает с анимационным решением данной задачи.

Enter of numbers of disks: 3 Enter the number of basic rod: 1 Enter the number of final rod: 3 1) 1 -> 3 2) 1 -> 2 3) 3 -> 2 4) 1 -> 3 5) 2 -> 1 6) 2 -> 3 7) 1 -> 3

Рисунок 5 — Рекурсия в С++

Из рисунка видно, что сначала перемещается диск со стержня один на стержень три, потом со стержня один на стержень два, со стержня три на стержень два и т. д. То есть программа всего лишь выдает последовательность перемещений дисков и минимальное количество шагов, за которые будут перемещены все диски.

Все эти задачи можно было решить итеративно. Возникает вопрос: “Как лучше решать, итеративно или рекурсивно?”. Отвечаю: “Недостаток рекурсии в том, что она затрачивает значительно больше компьютерных ресурсов, нежели итерация. Это выражается в большой нагрузке, как на оперативную память, так и на процессор. Если очевидно решение той или иной задачи итеративным способом, то им и надо воспользоваться иначе, использовать рекурсию!” В зависимости от решаемой задачи сложность написания программ изменяется при использовании того или иного метода решения. Но чаще задача, решённая рекурсивным методом с точки зрения читабельности кода, куда понятнее и короче.

В осточноукраинский национальный университет имени Владимира Даля

Рекурсия

Информатика и компьютерная техника

© Велигура А.В., кафедра экономической кибернетики, 2004

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

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

Что такое рекурсия?

Рекурсия происходит, если функция или подпрограмма вызывает сама себя. Прямая рекурсия (direct recursion) выглядит примерно так:

Function Factorial(num As Long) As Long

Factorial = num * Factorial(num - 1)

В случае косвенной рекурсии (indirectrecursion) рекурсивная процедура вызывает другую процедуру, которая, в свою очередь, вызывает первую:

Private Sub Ping(num As Integer)

Private Sub Pong(num As Integer)

Рекурсия полезна при решении задач, которые естественным образом разбиваются на несколько подзадач, каждая из которых является более простым случаем исходной задачи. Можно представить дерево в виде «ствола», на котором находятся два дерева меньших размеров. Тогда можно написать рекурсивную процедуру для рисования деревьев:

Private Sub DrawTree()

Нарисовать "ствол"

Нарисовать дерево меньшего размера, повернутое на -45 градусов

Нарисовать дерево меньшего размера, повернутое на 45 градусов

Хотя рекурсия и может упростить понимание некоторых проблем, люди обычно не мыслят рекурсивно. Они обычно стремятся разбить сложные задачи на задачи меньшего объема, которые могут быть выполнены последовательно одна за другой до полного завершения. Например, чтобы покрасить изгородь, можно начать с ее левого края и продолжать двигаться вправо до завершения. Вероятно, во время выполнения подобной задачи вы не думаете о возможности рекурсивной окраски - вначале левой половины изгороди, а затем рекурсивно - правой.

Для того чтобы думать рекурсивно, нужно разбить задачу на подзадачи, которые затем можно разбить на подзадачи меньшего размера. В какой‑то момент подзадачи становятся настолько простыми, что могут быть выполнены непосредственно. Когда завершится выполнение подзадач, большие подзадачи, которые из них составлены, также будут выполнены. Исходная задача окажется выполнена, когда будут все выполнены образующие ее подзадачи.

1. Опасности рекурсии

   1. Бесконечная рекурсия

Наиболее очевидная опасность рекурсии заключается в бесконечной рекурсии. Если неправильно построить алгоритм, то функция может пропустить условие остановки рекурсии и выполняться бесконечно. Проще всего совершить эту ошибку, если просто забыть о проверке условия остановки, как это сделано в следующей ошибочной версии функции факториала. Поскольку функция не проверяет, достигнуто ли условие остановки рекурсии, она будет бесконечно вызывать сама себя.

Private Function BadFactorial(num As Integer) As Integer

BadFactorial = num * BadFactorial (num - 1)

Функция также может вызывать себя бесконечно, если условие остановки не прекращает все возможные пути рекурсии. В следующей ошибочной версии функции факториала, функция будет бесконечно вызывать себя, если входное значение - не целое число, или если оно меньше 0. Эти значения не являются допустимыми входными значениями для функции факториала, поэтому в программе, которая использует эту функцию, может потребоваться проверка входных значений. Тем не менее, будет лучше, если функция выполнит эту проверку сама.

Private Function BadFactorial2(num As Double) As Double

BadFactorial2 = 1

BadFactorial2 = num * BadFactorial2(num-1)

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

Private Function BadFib(num As Double) As Double

BadFib = BadPib(num - 1) + BadFib (num - 2)

И последняя проблема, связанная с бесконечной рекурсией, заключается в том, что «бесконечная» на самом деле означает «до тех пор, пока не будет исчерпано стековое пространство». Даже корректно написанные рекурсивные процедуры будут иногда приводить к переполнению стека и аварийному завершению работы. Следующая функция, которая вычисляет сумму N + (N - 1) + … + 2 +1, приводит к исчерпанию стекового пространства при больших значенияхN. Наибольшее возможное значениеN, при котором программа еще будет работать, зависит от конфигурации вашего компьютера.

Private Function BigAdd(N As Double) As Double

If N <= 1 Then

BigAdd=N + BigAdd(N - 1)

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

Рекурсия — это свойство объекта подражать самому себе. Объект является рекурсивным если его части выглядят также как весь объект. Рекурсия очень широко применяется в математике и программировании:

• структуры данных:
  • граф (в частности деревья и списки) можно рассматривать как совокупность отдельного узла и подграфа (меньшего графа);
  • строка состоит из первого символа и подстроки (меньшей строки);
• шаблоны проектирования, например . Объект декоратора может включать в себя другие объекты, также являющиеся декораторами. Детально рекурсивные шаблоны изучил Мак-Колм Смит, выделив в своей книге общий шаблон проектирования — Recursion ;
• рекурсивные функции (алгоритмы) выполняют вызов самих себя.

Статья посвящена анализу трудоемкости рекурсивных алгоритмов, приведены необходимые математические сведения, рассмотрены примеры. Кроме того, описана возможность замены рекурсии циклом, хвостовая рекурсия.

Примеры рекурсивных алгоритмов

Рекурсивный алгоритм всегда разбивает задачу на части, которые по своей структуре являются такими же как исходная задача, но более простыми. Для решения подзадач функция вызывается рекурсивно, а их результаты каким-либо образом объединяются. Разделение задачи происходит лишь тогда, когда ее не удается решить сразу (она является слишком сложной).

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

Поиск элемента массива

Алгоритм делит исходный массив на две части — первый элемент и массив из остальных элементов. Выделяется два простых случая, когда разделение не требуется — обработаны все элементы или первый элемент является искомым.

В алгоритме поиска разделять массив можно было бы и иначе (например пополам), но это не сказалось бы на эффективности. Если массив отсортирован — то его деление пополам целесообразно, т.к. на каждом шаге количество обрабатываемых данных можно сократить на половину.

Двоичный поиск в массиве

Двоичный поиск выполняется над отсортированным массивом. На каждом шаге искомый элемент сравнивается со значением, находящимся посередине массива. В зависимости от результатов сравнения либо левая, либо правая части могут быть «отброшены».

Начало; binary_search(array, begin, end, element) ; выполняет поиск элемента со значением element ; в массиве упорядоченном по возрастанию массиве array ; между индексами begin и end если begin > end конец; вернуть false - элемент не найден mid:= (end + begin) div 2; вычисление индекса элемента посередине рассматриваемой части массива если array = element конец; вернуть true (элемент найден) если array < element результат:= binary_search(array, mid+1, end, element) иначе результат:= binary_search(array, begin, mid, element) конец; вернуть результат

Вычисление чисел Фибоначчи

Числа Фибоначчи определяются рекуррентным выражением, т.е. таким, что вычисление элемента которого выражается из предыдущих элементов: \(F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}, n > 2\).

Начало; fibonacci(number) если number = 0 конец; вернуть 0 если number = 1 конец; вернуть 1 fib_1:= fibonacci(number-1) fib_2:= fibonacci(number-2) результат:= fib_1 + fib_2 конец; вернуть результат

Быстрая сортировка (quick sort)

Алгоритм быстрой сортировки на каждом шаге выбирает один из элементов (опорный) и относительно него разделяет массив на две части, которые обрабатываются рекурсивно. В одну часть помещаются элементы меньше опорного, а в другую — остальные.

Блок-схема алгоритма быстрой сортировки

Сортировка слиянием (merge sort)

В основе алгоритма сортировки слиянием лежит возможность быстрого объединения упорядоченных массивов (или списков) так, чтобы результат оказался упорядоченным. Алгоритм разделяет исходный массив на две части произвольным образом (обычно пополам), рекурсивно сортирует их и объединяет результат. Разделение происходит до тех пор, пока размер массива больше единицы, т.к. пустой массив и массив из одного элемента всегда отсортированы.

На каждом шаге слияния из обоих списков выбирается первый необработанный элемент. Элементы сравниваются, наименьший из них добавляется к результату и помечается как обработанный. Слияние происходит до тех пор, пока один из списков не окажется пуст.

Начало; merge(Array1, Size1, Array2, Size2) ; исходные массивы упорядочены; в результат формируется упорядоченный массив длины Size1+Size2 i:= 0, j:= 0 вечный_цикл если i >= Size1 дописать элементы от j до Size2 массива Array2 в конец результата выход из цикла если j >= Size2 дописать элементы от i до Size1 массива Array1 в конец результата выход из цикла если Array1[i] < Array2[j] результат := Array1[i] i:= i + 1 иначе (если Array1[i] >= Array2[j]) результат := Array2[j] j:= j + 1 конец; вернуть результат

Анализ рекурсивных алгоритмов

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

\(
\begin{equation*}
T^{search}_n = \begin{cases}
\mathcal{O}(1) \quad &\text{$n = 0$} \\
\mathcal{O}(1) + \mathcal{O}(T^{search}_{n-1}) \quad &\text{$n > 0$}
\end{cases}
\end{equation*}
\)

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

Метод подстановки (итераций)

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

\(
T^{search}_n = \mathcal{O}(1) + \mathcal{O}(T^{search}_{n-1}) =
2\times\mathcal{O}(1) + \mathcal{O}(T^{search}_{n-2}) =
3\times\mathcal{O}(1) + \mathcal{O}(T^{search}_{n-3})
\)

Можно предположить, что \(T^{search}_n = T^{search}_{n-k} + k\times\mathcal{O}(1)\), но тогда \(T^{search}_n = T^{search}_{0} + n\times\mathcal{O}(1) = \mathcal{O}(n)\).

Мы вывели формулу, однако первый шаг содержит предположение, т.е. не имеется доказательства соответствия формулы рекуррентному выражению — получить доказательство позволяет метод математической индукции.

Метод математической индукции

Позволяет доказать истинность некоторого утверждения (\(P_n\)), состоит из двух шагов:

1. доказательство утверждения для одного или нескольких частных случаев \(P_0, P_1, …\);
2. из истинности \(P_n\) (индуктивная гипотеза) и частных случаев выводится доказательство \(P_{n+1}\).

Докажем корректность предположения, сделанного при оценки трудоемкости функции поиска (\(T^{search}_n = (n+1)\times\mathcal{O}(1)\)):

1. \(T^{search}_{1} = 2\times\mathcal{O}(1)\) верно из условия (можно подставить в исходную рекуррентную формулу);
2. допустим истинность \(T^{search}_n = (n+1)\times\mathcal{O}(1)\);
3. требуется доказать, что \(T^{search}_{n+1} = ((n+1)+1)\times\mathcal{O}(1) = (n+2)\times\mathcal{O}(1)\);
   1. подставим \(n+1\) в рекуррентное соотношение: \(T^{search}_{n+1} = \mathcal{O}(1) + T^{search}_n\);
   2. в правой части выражения возможно произвести замену на основании индуктивной гипотезы: \(T^{search}_{n+1} = \mathcal{O}(1) + (n+1)\times\mathcal{O}(1) = (n+2)\times\mathcal{O}(1)\);
   3. утверждение доказано.

Часто, такое доказательство — достаточно трудоемкий процесс, но еще сложнее выявить закономерность используя метод подстановки. В связи с этим применяется, так называемый, общий метод .

Общий (основной) метод решения рекуррентных соотношений

Общий метод не является универсальным, например с его помощью невозможно провести оценку сложности приведенного выше алгоритма вычисления чисел Фибоначчи. Однако, он применим для всех случаев использования подхода «разделяй и властвуй» :

\(T_n = a\cdot T(\frac{n}{b})+f_n; a, b = const, a \geq 1, b > 1, f_n > 0, \forall n\).

Уравнения такого вида получаются если исходная задача разделяется на a подзадач, каждая из которых обрабатывает \(\frac{n}{b}\) элементов. \(f_n\) — трудоемкость операций разбиения задачи на части и комбинирование решений. Помимо вида соотношения, общий метод накладывает ограничения на функцию \(f_n\), выделяя три случая:

1. \(\exists \varepsilon > 0: f_n = \mathcal{O}(n^{\log_b a — \varepsilon}) \Rightarrow T_n = \Theta(n^{\log_b a})\);
2. \(f_n = \Theta(n^{\log_b a}) \Rightarrow T_n = \Theta(n^{\log_b a} \cdot \log n)\);
3. \(\exists \varepsilon > 0, c < 1: f_n = \Omega(n^{\log_b a + \varepsilon}), f_{\frac{n}{b}} \leq c \cdot f_n \Rightarrow T_n = \Theta(f_n)\).

Правильность утверждений для каждого случая доказана формально . Задача анализа рекурсивного алгоритма теперь сводится к определению случая основной теоремы, которому соответствует рекуррентное соотношение.

Анализ алгоритма бинарного поиска

Алгоритм разбивает исходные данные на 2 части (b = 2), но обрабатывает лишь одну из них (a = 1), \(f_n = 1\). \(n^{\log_b a} = n^{\log_2 1} = n^0 = 1\). Функция разделения задачи и компоновки результата растет с той же скоростью, что и \(n^{\log_b a}\), значит необходимо использовать второй случай теоремы:

\(T^{binarySearch}_n = \Theta(n^{\log_b a} \cdot \log n) = \Theta(1 \cdot \log n) = \Theta(\log n)\).

Анализ алгоритма поиска

Рекурсивная функция разбивает исходную задачу на одну подзадачу (a = 1), данные делятся на одну часть (b = 1). Мы не можем использовать основную теорему для анализа этого алгоритма, т.к. не выполняется условие \(b > 1\).

Для проведения анализа может использоваться метод подстановки или следующие рассуждения: каждый рекурсивный вызов уменьшает размерность входных данных на единицу, значит всего их будет n штук, каждый из которых имеет сложность \(\mathcal{O}(1)\). Тогда \(T^{search}_n = n \cdot \mathcal{O}(1) = \mathcal{O}(n)\).

Анализ алгоритма сортировки слиянием

Исходные данные разделяются на две части, обе из которых обрабатываются: \(a = 2, b = 2, n^{\log_b a} = n\).

При обработке списка, разделение может потребовать выполнения \(\Theta(n)\) операций, а для массива — выполняется за постоянное время (\(\Theta(1)\)). Однако, на соединение результатов в любом случае будет затрачено \(\Theta(n)\), поэтому \(f_n = n\).

Используется второй случай теоремы: \(T^{mergeSort}_n = \Theta(n^{\log_b a} \cdot \log n) = \Theta(n \cdot \log n)\).

Анализ трудоемкости быстрой сортировки

В лучшем случае исходный массив разделяется на две части, каждая из которых содержит половину исходных данных. Разделение потребует выполнения n операций. Трудоемкость компоновки результата зависит от используемых структур данных — для массива \(\mathcal{O}(n)\), для связного списка \(\mathcal{O}(1)\). \(a = 2, b = 2, f_n = b\), значит сложность алгоритма будет такой же как у сортировки слиянием: \(T^{quickSort}_n = \mathcal{O}(n \cdot \log n)\).

Однако, в худшем случае в качестве опорного будет постоянно выбираться минимальный или максимальный элемент массива. Тогда \(b = 1\), а значит, мы опять не можем использовать основную теорему. Однако, мы знаем, что в этом случае будет выполнено n рекурсивных вызовов, каждый из которых выполняет разделение массива на части (\(\mathcal{O}(n)\)) — значит сложность алгоритма \(T^{quickSort}_n = \mathcal{O}(n^2)\).

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

Хвостовая рекурсия и цикл

Анализ трудоемкости рекурсивных функций значительно сложнее аналогичной оценки циклов, но основной причиной, по которой циклы предпочтительнее являются высокие затраты на вызов функции.

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

Для реализации такого поведения используется стек (стек вызовов, call stack) — в него помещаются номер команды для возврата и информация о локальных переменных. Стек не является бесконечным, поэтому рекурсивные алгоритмы могут приводить к его переполнению, в любом случае на работу с ним может уходить значительная часть времени.

В ряде случаев рекурсивную функцию достаточно легко заменить циклом, например, рассмотренные выше . В некоторых случаях требуется более творческий подход, но чаще всего такая замена оказывается возможной. Кроме того, существует особый вид рекурсии, когда рекурсивный вызов является последней операцией, выполняемой функцией. Очевидно, что в таком случае вызывающая функция не будет каким-либо образом изменять результат, а значит ей нет смысла возвращать управление. Такая рекурсия называется хвостовой — компиляторы автоматически заменяют ее циклом.

Зачастую сделать рекурсию хвостовой помогает метод накапливающего параметра , который заключается в добавлении функции дополнительного аргумента-аккумулятора, в котором накапливается результат. Функция выполняет вычисления с аккумулятором до рекурсивного вызова. Хорошим примером использования такой техники служит функция вычисления факториала:
\(fact_n = n \cdot fact(n-1) \\
fact_3 = 3 \cdot fact_2 = 3 \cdot (2 \cdot fact_1) = 3\cdot (2 \cdot (1 \cdot fact_0)) = 6 \\
fact_n = factTail_{n, 1} \\
\\
factTail_{n, accumulator} = factTail(n-1, accumulator \cdot n)\\
factTail_{3, 1} = factTail_{2, 3} = factTail_{1, 6} = factTail_{0, 6} = 6
\)

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

Начало; fibonacci(number) вернуть fibonacci(number, 1, 1, 0) конец начало; fibonacci(number, iterator, fib1, fib2) если iterator == number вернуть fib1 вернуть fibonacci(number, iterator + 1, fib1 + fib2, fib1) конец

Функция с накапливающим параметром возвращает накопленный результат, если рассчитано заданное количество чисел, в противном случае — увеличивает счетчик, рассчитывает новое число Фибоначчи и производит рекурсивный вызов. Оптимизирующие компиляторы могут обнаружить, что результат вызова функции без изменений передается на выход функции и заменить его циклом. Такой прием особенно актуален в функциональных и логических языках программирования, т.к. в них программист не может явно использовать циклические конструкции.

Литература

1. Многопоточный сервер Qt. Пул потоков. Паттерн Decorator[Электронный ресурс] – режим доступа : https://сайт/archives/1390. Дата обращения: 21.02.2015.
2. Джейсон Мак-Колм Смит : Пер. с англ. - М. : ООО “И.Д. Вильямс”, 2013. - 304 с.
3. Скиена С. Алгоритмы. Руководство по разработке.-2-е изд.: пер. с англ.-СПб.:БХВ-Петербург, 2011.-720с.: ил.
4. Васильев В. С. Анализ сложности алгоритмов. Примеры [Электронный ресурс] – режим доступа: https://сайт/archives/1660. Дата обращения: 21.02.2015.
5. А.Ахо, Дж.Хопкрофт, Дж.Ульман, Структуры данных и алгоритмы, М., Вильямс, 2007.
6. Миллер, Р. Последовательные и параллельные алгоритмы: Общий подход / Р. Миллер, Л. Боксер; пер. с англ. - М. : БИНОМ. Лаборатория знаний, 2006. - 406 с.
7. Сергиевский Г.М. Функциональное и логическое программирование: учеб. пособие для студентов высш. учеб. заведений / Г.М. Сергиевский, Н.Г. Волченков. - М.: Издательский центр «Академия», 2010.- 320с.

Рекурсии являются интересными событиями сами по себе, но в программировании они представляют особенную важность в отдельных случаях. Впервые сталкиваясь с ними, довольно значительное количество людей имеют проблемы с их пониманием. Это связано с огромным полем потенциального применения самого термина в зависимости от контекста, в котором «рекурсия» используется. Но можно надеяться, что эта статья поможет избежать возможного недоразумения или непонимания.

Что такое "рекурсия" вообще?

Слово "рекурсия" имеет целый спектр значений, которые зависят от области, в которой оно применяется. Универсальное обозначение является таким: рекурсии - это определения, изображения, описания объектов или процессов в самих объектах. Возможны они только в тех случаях, когда объект является частью самого себя. По-своему определяют рекурсию математика, физика, программирование и ряд других научных дисциплин. Практическое применение она нашла в работе информационных систем и физических экспериментах.

Что подразумевают под рекурсией в программировании?

Рекурсивными ситуациями, или рекурсией в программировании, называют моменты, когда процедура или функция программы вызывает саму себя. Как бы странно для тех, кто начал изучать программирование, это ни звучало, здесь нет ничего странного. Следует запомнить, что рекурсии - это не сложно, и в отдельных случаях они заменяют циклы. Если компьютеру правильно задать вызов процедуры или функции, он просто начнёт её выполнять.

Рекурсия может быть конечной или бесконечной. Для того чтобы первая прекратила сама себя вызывать, в ней же должны быть условия прекращения. Это может быть уменьшение значения переменной и при достижении определённого значения остановка вызова и завершение программы/переход к последующему коду, в зависимости от потребностей достичь определённых целей. Под бесконечной рекурсией подразумевают, что она будет вызываться, пока будет работать компьютер или программа, в которой она работает.

Возможна также организация сложной рекурсии с помощью двух функций. Допустим, есть А и Б. Функция А имеет в своем коде вызов Б, а Б, в свою очередь, указывает компьютеру на необходимость выполнить А. Сложные рекурсии - это выход из целого ряда сложных логических ситуаций для компьютерной логики.

Если читающий эти строки изучал программные циклы, то он, наверное, уже заметил схожесть между ними и рекурсией. В целом они действительно могут выполнять похожие или идентичные задания. С помощью рекурсии удобно делать имитацию работы цикла. Особенно это полезно там, где сами циклы использовать не очень удобно. Схема программной реализации не сильно различается у разных высокоуровневых языков программирования. Но всё же рекурсия в "Паскале" и рекурсия в С или другом языке имеет свои особенности. Может она быть успешно реализована и в низкоуровневых языках вроде "Ассемблера", но это является более проблематичным и затратным по времени.

Деревья рекурсии

Что такое "дерево" в программировании? Это конечное множество, состоящее как минимум из одного узла, который:

1. Имеет начальный специальный узел, который называют корнем всего дерева.
2. Остальные узлы находятся в количестве, отличном от нуля, попарно непересекающихся подмножеств, при этом они тоже являются деревом. Все такие формы организации называют поддеревьями главного дерева.

Другими словами: деревья содержат поддеревья, которые содержат ещё деревья, но в меньшем количестве, чем предыдущее дерево. Так продолжается до тех пор, пока в одном из узлов не останется возможности продвигаться далее, и это будет обозначать конец рекурсии. Есть ещё один нюанс насчет схематического изображения: обычные деревья растут снизу вверх, а в программировании они рисуются наоборот. Узлы, не имеющие продолжения, называются конечными узлами. Для удобства обозначения и для удобства используется генеалогическая терминология (предки, дети).

Зачем она применяется в программировании?

Своё применение рекурсия в программировании нашла в решении целого ряда сложных задач. Если необходимо сделать только один вызов, то более легким является применение интеграционного цикла, но при двух и более повторах, чтобы избежать построения цепочки и сделать их выполнение в виде дерева, и применяются рекурсивные ситуации. Для широкого класса задач организация вычислительного процесса таким способом является наиболее оптимальной с точки зрения потребления ресурсов. Так, рекурсия в "Паскале" или другом любом высокоуровневом языке программирования представляет собой вызов функции или процедуры до выполнения условий, независимо от количества внешних вызовов. Другими словами, в программе может быть только одно обращение к подпрограмме, но происходить оно будет до определённого заранее момента. В некотором роде это аналог цикла со своей спецификой использования.

Отличия рекурсии в различных языках программирования

Несмотря на общую схему реализации и конкретное применение в каждом отдельном случае, рекурсия в программировании имеет свои особенности. Это может привести к сложности во время поиска необходимого материала. Но всегда следует помнить: если язык программирования вызывает функции или процедуры, значит, и вызов рекурсии - дело осуществимое. Но наиболее значимые её отличия проявляются при использовании низких и высоких языков программирования. Особенно это касается возможностей программной реализации. Исполнение в конечном итоге зависит от того, какая задача поставлена, в соответствии с ней и пишется рекурсия. Функции и процедуры используются разные, но их цель всегда одна - заставить вызвать самих себя.

Рекурсия - это легко. Как просто запомнить содержание статьи?

Для начинающих понять её, может быть, поначалу сложно, поэтому нужны примеры рекурсии или хотя бы один. Поэтому следует привести небольшой пример из бытовой жизни, который поможет понять саму суть этого механизма достижения целей в программировании. Возьмите два или больше зеркал, поставьте их так, чтобы в одном отображались все остальные. Можно увидеть, что зеркала отображают себя многократно, создавая эффект бесконечности. Вот рекурсии - это, образно говоря, отражения (их будет множество). Как видите, понять несложно, было бы желание. А изучая материалы по программированию, далее можно понять, что рекурсия - это ещё и очень легко выполнимая задача.

Под этим словом подразумевается процесс, обозначающий повторение одних и тех же элементов «самоподобным образом». Достойный пример такого процесса — русская матрешка, и если бы не предел возможностей, то такая бы игрушка повторяла себя до бесконечности.

Исходя из технических причин, рекурсия все-таки величина конечная.

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

Примером математической рекурсии может служить уже всем изрядно надоевший пример — вычисление факториала. В действительности рекурсия в веб-программировании применяется довольно таки часто, а все потому, что рекурсия – это единственный вариант обхода любой стандартной структуры, когда точно не знают о ее реальных размерах и глубине вложения. Без нее также не обходится и построение графов. Это классический вариант.

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

Рекурсия в поисковых системах

Поисковые системы также зависят от рекурсии. Именно с того момента, когда был введен критерий авторитетности сайтов измерять количеством ссылок, поисковые системы также попались в эти сети. Ссылочная «масса» сайта складывается из мелких кусочков «масс» всех тех ресурсов, которые на него ссылаются. Чтобы высчитать этот показатель для одного сайта, необходимо просчитать «массу» всех ссылочных вариантов, которые в свою очередь состоят из других таких же компонентов, и так далее, по всей глубине поисковой сети. Вот вам и рекурсия на практике.

Рекурсивный PageRank oт Google

Такое имя носит алгоритм расчета, созданный и опубликованный Google. Этот алгоритм известен уже давно, но сколько бы раз он не преобразовывался и не дополнялся всевозможными усовершенствованиями, в основе лежит все тот же рекурсивный метод. Суть всегда остается одна и та же: расчеты, перерасчеты и еще раз перерасчеты. В результате получается опять та же функция.

Рекурсивный тИЦ от Яндекса

ТИЦ, созданный Яндексом, имеет точно такое же устройство, как и предыдущий алгоритм. Отличие заключается лишь в том, что он считается для всего сайта в целом, а не для каждой отдельной страницы. Именно поэтому поисковой системе Яндекс живется гораздо вольготнее, чем остальным, так как самих сайтов в разы меньше, чем страниц и пересчитать их намного легче.

Однако этот показатель на выдачу в Яндексе не влияет. Для этих целей у него есть глубоко спрятанный ВИЦ, который является аналогом PageRank. Так что объем подсчетов у Яндекс также немалый.

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

Прокомментировать эту статью:

Пожалуйста, зарегистрируйтесь для комментирования.