ДСо18-08-Рекурсия (Лекции Северов Часть 3)

Carnegie MellonРекурсияАлгоритмыи алгоритмические языкиgoo.gl/c8pyqxЛекция 8, 26 октября, 2018Лектор:Дмитрий Северов, кафедра информатики 608 КПМdseverov@mail.mipt.ruhttp://cs.mipt.ru/wp/?page_id=60771РекурсияСпособ конечного описаниябесконечных объектов.¢ Мощный метод решениязадач рекуррентнойприроды.¢ Использование стека дляорганизации неявногохранения наборов данных.¢Накладные расходы,связанные с обращениемфункции к себе.¢ Экспоненциальный росттрудоемкости в случаеопределения одногозначения по несколькимдругим.¢ Сложность поискаошибок и верификациипрограмм.¢2n! = 1 · 2 · 3 · 4 · … · nОт простого к сложному От сложного к простомуn! = n·(n-1)! и 1! = 1x1= 1 и xn= n·xn-1int x = 1;for(int i=2; i<=n; i++) x *= i;Итерацииint f(n) = n>1?n*f(n-1):1;Рекурсия3Формальное представлениеПусть:P – рекурсивная процедура;Si – базовые операции, не содержащие P;P – композиция операторов;¢ Тогда:¢P = P[Si,P]¢Средство создания рекурсивной процедуры- описание функций, которые определяют впроцедуре имена, по которым процедурасама себя вызывает.4Классификация и данныеПрямо рекурсивнаяP = P[Si,P]Косвенно рекурсивнаяP = P[Si,Q]Q = Q[Si,P]Переменные, определённые внутрирекурсивной функции, создаются заново прикаждом вызове такой функции.Идентификаторы всегда ссылаются напеременные, созданные последними.5Важно !¢Проблема окончания работы.P = P[ Si, if !B then P]Наиболее надежный способ окончанияработы – связать с Р параметр n ирекурсивно вызывать Р с параметром n-1:P(n) = P[Si, if n>0 then P(n-1)]¢Глубина рекурсии.Следует убедиться, что она не толькоконечна, но и достаточно мала.6Примеры использования рекурсии при решении задачПОИСК ПУТИ В ЛАБИРИНТЕ7своя строкасоздать свою отначала до концаприсвоитьстандартнуюприсвоить своюдобавитьсвоювыбрать символ в своейравна ли стандартнойравна ли своей8меньше ли своейбольше ли своейизмерить своюнайти свою в своейудалить своювывести своюввести свою9для карты лабиринтадля расстояний от началаввести массив своихотметить обратный путьотметить точку путисместиться к началуотметить оставшийся путь10дальшенекудаещё дальшедошлиначатьвывести легендувывести карту111213Сколько разбиений числа m на слагаемые ?65+14+24+1+13+33+2+12+2+22+2+1+11+1+1+1+1+13+1+1+12+1+1+1+1P(6) = 1114Сколько разбиений m на слагаемые £ nP(n) = Q(n,n)¢ Q(m,1) = 1¢ Q(1,n) = 1¢ Q(m,n) = Q(m,m)¢ Q(m,m) = 1 + Q(m,m-1)¢ Q(m,n) =Q(m-n,n) +¢Разбиения,содержащиеслагаемое, равное n1+1+…+1+1"n"n³mQ(m,n-1) " n < mРазбиения,не содержащиеслагаемое, равное n1516ЧИСЛА ФИБОНАЧЧИИли о том, что рекурсию следуетиспользовать весьма осмотрительно…17Вычисление чисел ФибоначчиИтеративныйРекурсивныйlong F(int n) {long F(int n) {long a=1,b=1;returndo { a+=b; b=a-b; }n<3 ? 1:F(n-1)+F(n-2);while(--n>2);}return a; }1819ФУНКЦИЯ АККЕРМАНАИли о том, когда рекурсию не следуетиспользовать вообще…20Функция Аккермана% + +,# = ,!(# − +, +),%=,!(#, %) = )!.# − +, !(#, % − +)/, #, % > 0#include <iostream>int A(int m,int n) { return!m ? n+1 : !n ? A(m-1,1) : A(m-1,A(m,n-1)); }void main() { int n,m;cout << "Input m="; cin >> m;cout << "Input n="; cin >> n;cout << "A("<< m << ',' << n << «)= " << A(m,n) <<endl;}21A(2,2) = A(1, A(2,1) )m\n012345678…0123456789n+11n+222n+332n+3-34…% + +,# = ,!(# − +, +),%=,!(#, %) = )!.# − +, !(#, % − +)/, #, % > 022Дерево вычисления функцииА(2,2)2,01,12,11,32,21,51,40,61,20,41,30,51,00,10,21,10,31,20,41,00,21,10,30,11,00,10,2А(2,2)=7 Количество вершин дерева - 27232425Биномиальные коэффициенты261.

На основе определенияint fact(int n) {switch (n) {case 0:case 1: return 1;default: return n*fact(n-1); }}…for(n=0; n<=N; n++) for(k=0; k<=n; k++)cout << fact(n)/fact(k)/fact(n-k) <<(n==k?'\n':' ');272. На основе рекуррентного соотношенияint Cnk(int n,int k) {if(!k) return 1;if(!n) return 1;if(n==k) return 1;return Cnk(n-1,k)+Cnk(n-1,k-1);}283. Треугольник Паскаля11111123401123 136 4 1 4void C(int N) {int *a, i, n;a = new int[++N];a[0]=1; if(N>1) a[1]=1;for(n=3; n<=N; n++) {for(i=n-2,a[n-1]=1; i>0; i--)a[i]+=a[i-1];for(i=0;i<n;i++)cout <<a[i]<<(i==n-1?'\n':' '); }delete a;}2930313233Правильные скобочные выражения()()()()()() (())()(())()(()) (()()) ((()))Вставка «()» до и после «(« до первой закрывающейся скобки«)»Избегая повторений вставки делаем перед каждойоткрывающейся скобкой и перед первой закрывающейся3435.