Рекурсия(Практика №1). Рекурсивные алгоритмы Рекурсия
 Скачать 34.12 Kb.
|
|
Рекурсия Сундукова Структуры и алгоритмы компьютерной обработки данных http://www.iprbookshop.ru/57384.html Стр. 36-50 - теория Теория Рекурсивные алгоритмы Рекурсия – фундаментальное понятие в математике и компьютерных науках. В языках программирования рекурсивной программой называется программа, которая обращается сама к себе (подобно тому, как в математике рекурсивная функция определяется через понятия самой этой функции). Рекурсивная программа не может вызывать себя до бесконечности, следовательно, вторая важная особенность рекурсивной программы – наличие условия завершения, позволяющее программе прекратить вызывать себя. Таким образом рекурсия в программировании может быть определена как сведение задачи к такой же задаче, но манипулирующей более простыми данными. Как следствие, рекурсивная программа должна иметь как минимум два пути выполнения, один из которых предполагает рекурсивный вызов (случай «сложных» данных), а второй – без рекурсивного вызова (случай «простых» данных). Примеры рекурсивных программ. В ряде случаев рекурсивную подпрограмму можно построить непосредственно из формального математического описания задачи.
Рекурсия и итерация. Рекурсивную программу всегда можно преобразовать в нерекурсивную (итеративную, использующую циклы), которая выполняет те же вычисления. И наоборот, используя рекурсию, любое вычисление, предполагающее использование циклов, можно реализовать, не прибегая к циклам. К примеру, вычисление факториала и чисел Фибоначчи можно реализовать без рекурсии:
При выполнении рекурсивной подпрограммы сначала происходит «рекурсивное погружение», а затем «возврат вычисленных результатов». Например, вычисление 5! при помощи вызова Fact(5) будет происходить следующим образом: Fact(5) 5 * Fact(4) 5 * 24 120 4* Fact(3) 4 * 6 3 * Fact(2) 3 * 2 2 * Fact(1) 2 * 1 1 1 Как видно на примере вычисления 5!, при «рекурсивном погружении» функция Fact вызывает точно такой же новый экземпляр самой себя. При этом сама функция как бы еще не завершилась, а новый ее экземпляр уже начинает работать. И только когда новый экземпляр завершит работу («вернет вычисленные результаты»), будет продолжена работа самой функции. Стек. Информация о таких незавершенных вызовах рекурсивных подпрограмм (а это, в самом простом представлении, значения переменных, необходимых для работы подпрограммы) запоминается в специальной области памяти – стеке. При работе в среде Turbo Pascal содержимое стека и весть процесс появления и завершения рекурсивных вызовов можно просмотреть в окне «Call Stack», которое вызывается нажатием клавиш Ctrl+F3. Размер стека по умолчанию – 16Кб. Если незавершенных рекурсивных вызов слишком много (хотя вы по ошибке могли написать и программу с бесконечной рекурсией – тогда вам ничто не поможет), то система выдаст сообщение «Stack overflow» («Переполнение стека»). В этом случае есть смысл увеличить размер стека используя меню «Options – Memory Sizes ”. Также помните, что нажав клавиши Ctrl+O O, вы перед текстом программы получите список значений всех директив компилятора Turbo Pascal, в котором можно изменять признаки их активности и значения, установленные по умолчанию. {$A+,B-,D+,E-,F-,G+,I-,L+,N+,O-,P-,Q-,R-,S-,T-,V+,X+} {$M 16384,0,655360} Размер стека определяется первым параметром директивы $M. Второй и третий ее параметры – нижняя и верхняя границы области динамически выделяемой памяти (кучи, heep). Размер стека можно увеличить непосредственно в такой строке, однако эти установки будут действовать только для данной программы. Сложность рекурсивных вычислений. При относительной простоте написания, у рекурсивных подпрограмм часто встречается существенный недостаток – неэффективность. Так, сравнивая скорость вычисления чисел Фибоначчи с помощью итеративной и рекурсивной функции можно заметить, что итеративная функция выполняется почти «мгновенно», не зависимо от значения n. При использовании же рекурсивной функции уже при n=40 заметна задержка при вычислении, а при больших n результат появляется весьма не скоро. Неэффективность рекурсии проявляется в том, что одни и те же вычисления производятся по многу раз. Так для вычисления 40-го числа Фибоначчи схема рекурсивных вызовов представлена на рисунке ниже.  Оценить сложность рекурсивных вычислений (количество рекурсивных вызовов) можно с помощью рекуррентных соотношений. Рекуррентное соотношение – это рекурсивная функция с целочисленными значениями. Значение любой такой функции можно определить, вычисляя все ее значения начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения. Рекуррентные выражения используются, в частности, для определения сложности рекурсивных вычислений. Например, пусть мы пытаемся вычислить числа Фибоначчи по рекурсивной схеме F(i) = F(i-1) + F(i-2), при N >= 1; F(0) = 1; F(1) = 1; с помощью указанной выше рекурсивной подпрограммы-функции F(n). Требующееся при вычислении значения F(N) по такой схеме количество рекурсивных вызовов может быть получено из решения рекуррентного выражения TN = TN-1 + TN-2, при N >= 1; T0 = 1; T1 = 1 TN приблизительно равно ФN , где Ф 1.618 - золотая пропорция («золотое сечение»), т.е. приведенная выше программа потребует экспоненциальных временных затрат на вычисления. Метод «разделяй и властвуй». Многие алгоритмы используют два рекурсивных вызова, каждый из которых работает приблизительно с половиной входных данных. Такая рекурсивная схема, по-видимому, представляет собой наиболее важный случай хорошо известного метода «разделяй и властвуй» (divide and conquer) разработки алгоритмов. В качестве примера рассмотрим задачу отыскания максимального из N элементов, сохраненных в массиве a[1], . . . , a[N] с элементами типа Item. Эта задача легко может быть решена за один проход массива: Max:=a[1]; For i:=1 to N do if a[i] > Max then Max:=a[i]; Рекурсивное решение типа «разделяй и властвуй» - еще один простой (хотя совершенно иной) способ решения той же задачи: Function Max (a : array of Item; l, r : integer) : Item; var u, v : Item; m : integer; begin m := (l+r) / 2; if (l = r) then Max := a[l] else begin u := Max (a, l, m); v := Max (a, m+1, r); if (u > v) then Max := u else Max := v end end; Чаще всего подход “разделяй и властвуй» используют из-за того, что он обеспечивает более быстрые решения, чем итерационные алгоритмы. Основным недостатком алгоритмов типа «разделяй и властвуй» является то, что делят задачи на независимые подзадачи. Когда подзадачи независимы, это часто приводит к недопустимо большим затратам времени, так как одни и те же подзадачи начинают решаться по многу раз. К примеру, приведенная выше рекурсивная схема вычисления чисел Фибоначчи абсолютно недопустима при больших значениях N, так как приводит к многократным повторным вычислениям, и экспоненциальной сложности вычислений (TN приблизительно равно ФN , где Ф 1.618 есть золотая пропорция). Обходить подобные ситуации позволяет подход, известный как динамическое программирование. Динамическое программирование. Общий подход для реализации рекурсивных программ, который дает возможность получать эффективные и элегантные решения для обширного класса задач. Технология, называемая восходящим динамическим программированием (bottom-up dynamic programming) основана на том, что значение рекурсивной функции можно определить, вычисляя все значения этой функции, начиная с наименьшего, используя на каждом шаге ранее вычисленные значения для подсчета текущего значения. Она применима к любому рекурсивному вычислению при условии, что мы можем позволить себе хранить все ранее вычисленные значения. Что в результате позволит уменьшить временную зависимость с экспоненциальной на линейную ! Нисходящее динамическое программирование (top-down dynamic programming) – еще более простая технология. Она позволяет выполнять рекурсивные функции при том же количестве итераций, что и восходящее динамическое программирование. Технология требует введения в рекурсивную программу неких средств, обеспечивающих сохранение каждого вычисленного значения и проверку сохраненных значений во избежание их повторного вычисления. К примеру, сохраняя вычисленные значения в статическом массиве K[1..100] (предварительно проинициализированном, к примеру, числом -1), мы явным образом исключим любые повторные вычисления. Приведенная ниже программа вычисляет F(N) за время, пропорциональное N. Function F( n : integer ) : longint; begin if (K[n] <> -1) then F := K[n] else if n < 2 then F := n else begin t := F(n-1) + F(n-2) K[n] := t; F := t end end; Примеры задач, решаемых с помощью рекурсии. Поиск максимального элемента массива. Поскольку текст функции для поиска максимального элемента массива приведен выше, остановимся лишь на особенностях ее применения. Type Item = integer; Const Mas : array [1..10] of Item = (3,6,2,4,1,8,0,9,5,7); Function Max (A : array of Item; l, r : integer) : Item; . . . . . end; begin writeln (Max(Mas,0,9)) {l=0, r=9 т.к. параметр A в списке формальных параметров функции Max – открытый массив, т.е. значения индексов начинаются от 0} end Поиск элемента в упорядоченном массиве (двоичный поиск). Имеется упорядоченный массив и эталонный элемент. Требуется определить, содержится ли эталон в массиве. Если «да», то вернуть соответствующий номер позиции. Если «нет» - вывести сообщение. Для решения задачи используется метод деления исходного массива пополам. С эталоном сравнивается «средний» (расположенный по середине) элемент массива. Если он меньше эталона – поиск продолжается в правой половине массива. Если меньше – в левой. Поиск ведется до тех пор, пока не будет обнаружено соответствие, или пока длина участков массива, в которых ведется поиск, не станет меньше 1. Type Item = integer; Const A : array[1..10] of Item = (1,2,3,4,5,6,7,8,9,10); Function Se (a : array of Item; e : Item; l, r : integer) : integer; {a – массив, е – эталон поиска, l, r – левая и правая границы подмассива, в котором производится поиск Функция возвращает позицию найденного элемента (нумерация от 0) или -1 } var m : integer; begin if (r=l) and (a[r]<>e) then Se:=-1 else begin m := (l+r) div 2; if (e = a[m]) then Se := m else if e < a[m] then Se := Se (a, e, l, m) else Se := Se (a, e, m+1, r) end; begin P:= Se(A,0,0,9); if P<>-1 then writeln(‘Искомый элемент в позиции ’, P+1) else writeln(‘Искомый элемент не присутствует в массиве’) end. Ханойские башни. Имеется три стержня A, B, C. На стержне А надето N колец, причем кольцо меньшего диаметра должно располагаться над кольцом большего диаметра. Требуется переместить N колец с А на С, используя В как промежуточный стержень. При перемещении колец кольцо меньшего диаметра можно класть поверх кольца большего диаметра, но не наоборот. Программа должна распечатать протокол перемещений (цепочку команд вида Х -> Y). Например, в случае N=3 исходную и конечную ситуацию можно изобразить так:  Протокол действий будет иметь вид: A C, A B, C B, (2) A C, (3) B A, B C, A C (4) Я не случайно записал протокол в три строки. Определим смысл действий, записанных в каждой из строк, и проиллюстрируем их:  (1) – Переместить N колец с А на С, используя В как промежуточный (2) – Переместить (N-1) кольцо с А на В, используя С как промежуточный (3) – Переместить кольцо с А на С (4) – Переместить (N-1) кольцо с В на С, используя А как промежуточный К тому же (1) = (2) (3) (4). Т.е. исходная задача (1), работающая с N кольцами, сводится рекурсивно к таким же по сути задачам (2) и (4), в которых используется (N ‑ 1) кольцо. Программная реализация решения: Procedure Towers(n:byte; A, C, B : char) {переложить N колец с А на С, используя В как промежуточный} begin if n=1 then writeln(A, ‘ ’, C) else begin Towers(n-1, A, B, C); writeln(A, ‘ ‘, C); Towers(n-1, B, C, A) end end; begin Towers(4, ‘A’, ‘C’, ‘B’) { решаем задачу при N = 4 } end. Деревья. Изучение рекурсии неразрывно связано с изучением рекурсивно определяемых структур данных, называемых деревьями (trees). Деревья используются как для упрощения понимания и анализа рекурсивных программ, так и в качестве явных структур данных. В свою очередь, рекурсивные программы используются для построения деревьев. Глобальная связь между ними (и рекуррентными отношениями) используется при анализе алгоритмов. Деревья рассмотрим позже, в теме «Динамические структуры данных». Варианты заданий Размен денег. Имеется некоторая сумма денег S и набор монет с номиналами a1, …, an. Монета каждого номинала имеется в единственном экземпляре. Необходимо найти все возможные способы разменять сумму S при помощи этих монет. Точная степень двойки Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае. Операцией возведения в степень пользоваться нельзя! Сумма цифр числа Дано натуральное число N. Вычислите сумму его цифр. При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Цифры числа справа налево Дано натуральное число N. Выведите все его цифры по одной, в обратном порядке, разделяя их пробелами или новыми строками. При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика. Цифры числа слева направо Дано натуральное число N. Выведите все его цифры по одной, в обычном порядке, разделяя их пробелами или новыми строками. При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика. Проверка числа на простоту Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное. Алгоритм должен иметь сложность O(logn). Указание. Понятно, что задача сама по себе нерекурсивна, т.к. проверка числа n на простоту никак не сводится к проверке на простоту меньших чисел. Поэтому нужно сделать еще один параметр рекурсии: делитель числа, и именно по этому параметру и делать рекурсию. Палиндром Дано слово, состоящее только из строчных латинских букв. Проверьте, является ли это слово палиндромом. Выведите YES или NO. При решении этой задачи нельзя пользоваться циклами, в решениях на питоне нельзя использовать срезы с шагом, отличным от 1 Вывести нечетные числа последовательности Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите все нечетные числа из этой последовательности, сохраняя их порядок. В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции. Вывести члены последовательности с нечетными номерами Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите первое, третье, пятое и т.д. из введенных чисел. Завершающий ноль выводить не надо. В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции. Максимум последовательности Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите наибольшее значение числа в этой последовательности. В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция возвращает единственное значение: максимум считанной последовательности. Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля). Среднее значение последовательности Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите среднее значение элементов этой последовательности (без учета последнего нуля). В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает кортеж из пары чисел: число элементов в последовательности и их сумма. В программе на языке C++ результат записывается в две переменные, которые передаются в функцию по ссылке. Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля). Второй максимум Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите значение второго по величине элемента в этой последовательности, то есть элемента, который будет наибольшим, если из последовательности удалить наибольший элемент. В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает. Гарантируется, что последовательность содержит хотя бы два числа (кроме нуля). Количество элементов, равных максимуму Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите, какое количество элементов этой последовательности, равны ее наибольшему элементу. В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает. Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля). Количество единиц Дана последовательность натуральных чисел (одно число в строке), завершающаяся двумя числами 0 подряд. Определите, сколько раз в этой последовательности встречается число 1. Числа, идущие после двух нулей, необходимо игнорировать. В этой задаче нельзя использовать глобальные переменные и параметры, передаваемые в функцию. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметров. Заданная сумма цифр Даны натуральные числа k и s. Определите, сколько существует k-значных натуральных чисел, сумма цифр которых равна d. Запись натурального числа не может начинаться с цифры 0. В этой задаче можно использовать цикл для перебора всех цифр, стоящих на какой-либо позиции. Без двух нулей Даны числа a и b. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом. Разворот числа Дано число n, десятичная запись которого не содержит нулей. Получите число, записанное теми же цифрами, но в противоположном порядке. При решении этой задачи нельзя использовать циклы, строки, списки, массивы, разрешается только рекурсия и целочисленная арифметика. Фунция должна возвращать целое число, являющееся результатом работы программы, выводить число по одной цифре нельзя. | ||||||||||||||||||||