Лекция № 12

Тема: «Рекурсивные функции и алгоритмы»

 

План лекции

1. Рекурсия и итерация

2. Методы и проблемы анализа сложности рекурсивных алгоритмов

3. Рекурсивные подпрограммы

4. Примеры иллюстрации рекурсии

 

1. Рекурсия и итерация

В математике и программировании рекурсия – это метод определения или выражения функции или процедуры посредством той же функции и процедуры. Рекурсию обычно рассматривают в качестве антипода итерации. Соответственно различают два больших класса алгоритмов: итерационные и рекурсивные. В основе итерационных алгоритмов лежит итерация – многократное повторение одних и тех же действий. Структура таких алгоритмов хорошо описывается алгоритмическими конструкциями “следование”, “ветвление”, “цикл”.

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

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

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

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

 

2. Методы и проблемы анализа сложности

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

Основными современными инструментами исследования сложности рекурсивных алгоритмов являются метод рекуррентных соотношений и теоретико-графовый метод исследования дерева рекурсии. Идея метода рекуррентных соотношений состоит в построении и решении рекуррентного соотношения, которому удовлетворяет функция сложности t(n) алгоритма. Найденное решение позволяет получить O-оценку для t(n). Этот метод не является универсальным. Во-первых, он применим только для оценки временной сложности рекурсивных алгоритмов. Оценка емкостной сложности требует учета глубины рекурсии и, как следствие, других инструментов. Во-вторых, метод рекуррентных соотношений позволяет получить лишь верхние оценки временной сложности рекурсивных алгоритмов, т.е. только для худшего случая. В-третьих, рекуррентное соотношение для t(n) удается найти только тогда, когда преобразование, уменьшающее значение параметра рекурсии n, линейно относительно n.

Если рекуррентное соотношение для t(n) все же найдено, то нет никакой гарантии, что удастся установить явную форму или хотя бы асимптотическую оценку для t(n). Проблема в том, что общих методов решения рекуррентных соотношений нет. Известны лишь методы решения некоторых классов рекуррентных соотношений. Тем не менее, во многих практических ситуациях выход находится. Так, допустимо использование общих приемов решения линейных рекуррентных соотношений с постоянными коэффициентами, аппарата производящих функций и интегральных методов [2]–[5]. Наконец, относительно хорошо решаются рекуррентные соотношения, характерные для прямой рекурсии, организованной по принципу “разделяй и властвуй” и аддитивным уменьшением размерности задачи на некоторую константу. Здесь имеются две основные теоремы о рекуррентных соотношениях, одна из которых доказывается в настоящей статье. Данные теоремы — удобный математический инструмент анализа сложности двух наиболее типичных принципов организации рекурсии, применяемых в практике разработки алгоритмов и программ. Их использование позволяет избежать утомительных расчетов и выбрать наименее трудоемкую схему организации рекурсии.

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

 

3. Рекурсивные подпрограммы 

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

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

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

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

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

 

Типичная рекурсивная процедура имеет вид:

тип Rec (int n)

{

  действие на входе рекурсию;

  if (проверка условия)

Rec(n-1);

  else   действия на выходе из рекурсии;

}

 

ВЫВОД

Для реализации рекурсивной подпрограммы необходимо:

1)      Знать граничное (базовое) решение

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

 

4. Примеры иллюстрации рекурсии

ПРИМЕР 1. Разработаем программу, в которой объявлена рекурсивная функция, вычисляющая n!

Для вычисления факториала знаем, что:

1)      1! = 1 и 0! = 1 – граничное решение

2)      Формула для расчета факториала с помощью рекурсивной функции:

n!=n*(n-1)!

Для функции fact() был объявлен тип данных unsigned long int, так как значение факториала возрастает очень быстро, например уже 10! = 3 628 800. Если не хватит размера типа данных, то в результате мы получим совсем не правильное значение.

Обратите внимание на выделенные строки кода, строки 18, 20, 21 — это рекурсивное решение n!. Строки 18, 20, являются базовым решением рекурсивной функции, то есть, как только значение в переменной f  будет равно 1 или 0 (так как мы знаем, что 1! = 1 и 0! = 1), прекратятся рекурсивные вызовы, и начнут возвращаться значения, для каждого рекурсивного вызова. Когда вернётся значение для первого рекурсивного вызова, программа вернёт значение вычисляемого факториала. В строке 21 функция fact() вызывает саму себя, но уже её аргумент на единицу меньше. Аргумент каждый раз уменьшается, чтобы достичь частного решения.

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

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

 

 

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

 

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

 

 

ПРИМЕР 2. Рассмотрим ещё одну типичную задачу — нахождение чисел Фибоначчи, используя рекурсию.

1)      Первое и второе значения должны быть заданы, их значения равны единице. Это граничные условия. Т.е. при n=1 или n=2 числа Фибоначчи равны 1.

2)      Числа Фибоначчи составляют последовательность, очередной элемент которой вычисляется по двум предыдущим значениям:

Fn=Fn-1 + Fn-2

Это формула для реализации рекурсии.

 

Далее приведен код рекурсивного решения такой задачи. Вводим порядковый номер числа из ряда Фибоначчи, и программа выдает число Фибоначчи с введенным номером.

 

 

Изменим программу для решения такой задачи:

Вводим порядковый номер числа из ряда Фибоначчи, и программа найдёт все числа из ряда Фибоначчи, порядковые номера которых меньше либо равны введённого.

 

 

ПРИМЕР 3. Вычислить сумму элементов линейного массива.

 

При решении задачи используем следующие соображения:

1)      сумма массива равна нулю, если количество элементов равно нулю

2)      сумма массива равна сумме всех предыдущих элементов плюс последний, если количество элементов не равно нулю:

s=s+a[n]

 

 

ПРИМЕР 4. Функция , для вычисления биномиального коэффициента  по следующей формуле  при  является рекурсивной.

           

int C(int m, int n)

            {

    int f;

    if (m==0||m==n) f=1;

else f=C(m, n-1)+C(m-1, n-1);

    return f;

  }

 

Контрольные вопросы.

1.      Для чего применяют рекурсию?

2.      Когда не стоит применять рекурсию?

3.      Что является базой рекурсии?

4.      Что является шагом рекурсии?

5.      Почему выполнение шагов рекурсии всегда приведёт к базе?

6.      Какова будет глубина рекурсии при данном значении аргументов?

7.      Как растёт размер дерева рекурсивных вызовов при увеличении входных данных? Будут ли повторяющиеся вызовы в этом дереве и имеет ли смысл делать рекурсию с запоминанием?

8.      Примеры рекурсивных программ

9.      Рекурсивная обработка деревьев

10.  Проблемы анализа сложности алгоритмов