Рекурентни редици и рекурсия
Recurrence Relations and Recursion: A method for teaching the topic of “Recursion” in the programming course is developed in this article. It also uses the recurrent-sequences knowledge, gained from discrete-mathematics course.
Рекурсията е един от методите, даващ възможност за постигане на кратко и елегантно решение на определен клас задачи. В същото време тя е една от „парливите” теми в обучението по програмиране. Една от причините за това е, че в много от случаите, когато за съответната задача съществува итеративно решение, се препоръчва избягване на рекурсията. Друга причина са трудностите при преподаването и усвояването на темата. Оказва се, че същността на рекурсията като метод за решаване на даден проблем, най-често остава неразбрана за по-голямата част от обучаемите. Предмет на настоящата статия е един подход за представяне на принципите на рекурсията пред студентите в курса по Програмиране, като се използват знанията за рекурентни редици, получени в курса по Дискретна математика.
Рекурентни редици и рекурсия
Сама по себе си рекурсията не е алгоритъм, а метод за построяване на алгоритми. Тя съвсем естествено може да бъде приложена в случаите, когато решаването на дадена задача с определена размерност може да бъде сведено до решаването на аналогична задача с по-малка размерност. Това я доближава до същността на рекурентните редици – редици, при които всеки следващ елемент се получава от предходните по определено правило.
Определение 1. Нека редицата е редицата . Ако може да се изрази като функция на предишните елементи на редицата S,…,…,,21naaana
(1. 1) , ),…,,(121−=nnaaafa
то равенството (1.1) се нарича рекурентна зависимост и се казва, че редицата удовлетворява тази рекурентна зависимост. S
Определение 2. Нека е най-малкото цяло число, такова, че при определени стойности на равенството (1.1) определя еднозначно стойността на за . Стойностите се наричат начални условия за рекурентната зависимост. k k a a a ,…,,2 1 nakn>kaaa,…,,21
Задачите, за чието решение се изисква рекурсивен алгоритъм могат да бъдат групирани по следния начин:
1. По дадена рекурентна зависимост и съответни начални условия за нея, да се определи рекурсивна функция, пресмятаща –тия член на редица, удовлетворяваща тази рекурентна зависимост. n
Примерни задачи:
Зад. 1. 1. Да се напише рекурсивна функция за изчисляване на , където е редицата на Фибоначи, определена с рекурентната зависимост: nF,……,,,10nFFF
1,11021==+=−−FFFFFnnn
Зад. 1. 2. Да се напише рекурсивна функция за изчисляване стойността на функцията на Акерман , дефинирана за 0 с помощта на рекурентната зависимост: ),(nmAck,0≥≥nm МАТЕМАТИКА, ИНФОРМАТИКА И КОМПЮТЪРНИ НАУКИ
1),0(+=nnAck
)1,1()0,(−=mAckmAck
))1,(,1(),(−−=nmAckmAcknmAck за 0 ,0>>nm
2. Задачи, в които студентът трябва сам да определи рекурсивната стъпка. По даденото условие в задачата той трябва да реши по какъв начин да сведе задачата до еднотипна, но с по-малка размерност.
Примерни задачи:
Зад. 2. 1. Да се състави рекурсивна функция, която пресмята !n
Зад. 2. 2. Да се състави рекурсивна функция за определяне броя на цифрите на естествено число.
Зад. 2. 3. Да се състави рекурсивна функция, която генерира и извежда всички последователности от символите 0 и 1 с дължина и несъдържащи две последователни нули. n
Зад. 2. 4. Нека всеки ден имаме право да си купуваме точно от следните неща – сок за 1 лв., пица за 2 лв. или сандвич за 2 лв. Да се напише рекурсивна функция, отпечатваща начините, по които можем да изхарчим лв. n
3. Задачи, изискващи търсене с връщане назад – задачите от този тип не са предмет на настоящата статия и няма да бъдат разгледани тук..
Прави впечатление, че за студентите най-леки се оказват задачите от група 1, т. е. такива при които рекурсивната зависимост е дадена в явен вид. В този случай почти всички обучаеми успяват да реализират съответната рекурсивна функция. За по-голяма част от студентите обаче задачите от група 2 представляват значителна трудност. Често те не могат да съобразят коя от характеристиките в дадената задача може да бъде използвана с цел свеждане на задачата до решаването на аналогична, но с по-малка размерност. Това налага извода, че решаването на задачите от група 2 може да бъде подпомогнато, ако обучаемият бъде насочен към извеждането на съответната рекурентна зависимост и начални условия за нея. Така решаването на задача от група 2 се свежда до решаване на задача от група 1. Намирането на самата рекурентна зависимост подпомага определянето на рекурсивната стъпка, а съответните начални условия – граничните случаи за рекурсивния алгоритъм. Фактът, че студентите изучават рекурентни редици в курса по Дискретна математика значително улеснява този процес.
Като пример може да бъде разгледана една съвсем тривиална на пръв поглед задача от тип 2:
Задача. Да се състави рекурсивна функция, намираща сумата на числата от 1 до . n
Колкото и лека да изглежда тази задача, тя затруднява голяма част от обучаемите. Аналогичната й задача от рекурентни редици изглежда по следния начин:
Ако с означим сумата на числата от 1 до , да се намери рекурентната зависимост )и съответните начални условия. nSn(1−=nnSfS
Познавайки принципите при определяне на рекурентни зависимости студентите лесно могат да стигнат до нейното решение:
111=+=−SnSSnn
По този начин задачата се свежда до задача от тип 1, за която лесно може да бъде написана съответната рекурсивна функция:
int sum(int n)
{
if(n==1)return 1;
else return n+sum(n-1);
}
Анализът на условията на задачи от такъв тип показва, че те изискват да бъде направена някаква количествена оценка, т. е. рекурсивната функция да върне конкретна стойност(брой, сума, произведение, стойност на член от числова редица). В този случай има пълно съответствие от една страна между откритата рекурентна зависимост и рекурентната стъпка в рекурсивната функция и от друга – между началните условия при редиците и граничните случаи при рекурентните функции.
Съществуват задачи за съставяне на рекурсивна функция от група 2, при които решението не следва в явен вид решението на съответната задача от рекурентни зависимости.
Пример за такава задача е:
Задача. Един робот може да прави стъпки с дължина 1м и 2м. Да се състави рекурсивна функция, която отпечатва всички възможни начини, по които роботът може да измине м. n
Новото в тази задача е, че трябва да бъдат получени последователните стъпки, които трябва да направи робота. В този случай може да се разгледа помощна задача, аналогична на дадената, но изискваща количествена оценка:
Един робот може да прави стъпки с дължина 1м и 2м. Ако с се означи броя на начините, по които роботът може да измине м, да се определи рекурентната зависимост за редицата .() nSn,…,…,,21nSSS),(21−−=nnnSSfS
Разсъжденията за определяне на рекурентната зависимост са следните: Двете възможности за първа стъпка на робота са 1м или 2м. В първия случай му остават да измине още ) м, което може да бъде направено по начина, а във втория –м, изминати по начина. Схематично това може да бъде отразено така: 1(−n1−nS)2(−n2−nS
Окончателно за рекурентната зависимост се получава
21−−+=nnnSSS
Остава да бъдат определени съответните начални условия за и . 1S2S
1S е броят на начините, по които роботът може да измине 1м. За това съществува единствена възможност да направи крачка от 1м, т. е. 11=S
2Sе броят на начините, по които роботът може да измине 2 м. Това може да стане като направи една крачка от 2м или две крачки от по 1м, т. е. 22=S.
С това рекурентната зависимост за редицата е определена еднозначно. ,…,…,,21nSSS
Очевидно решението на изходната задача няма да използва в явен вид така определената рекурентна зависимост. Начинът, по който се разсъждава обаче, за получаването на рекурентната зависимост, дава идеята за рекурсивната стъпка на търсената функция, а на началните условия – за граничните случаи.
Нека в масива ] се пазят дължините на последователно направените от робота стъпки, а функцията print(p) печата последователността от [Napстъпки.
1м
S начина 1 −n
( )1 − n м
2м
S начина 2 −n
( )2 − n м МАТЕМАТИКА, ИНФОРМАТИКА И КОМПЮТЪРНИ НАУКИ Велико Търново 2006 401
Ако robo(k,n) е търсената рекурсивна функция, която определя и запазва в масива дължината на к-тата направена стъпка(n е оставащото разстояние), то може да се направи аналогия със съответните членове на рекурентната редица и да се определи рекурсивната стъпка и съответните гранични случаи: iS
За граничните случаи:
С се свързва robo(k,1). От направените разсъждения за се определят следните действия за robo(k,1): 1S1S
a[k]=1; print(k);
?? С се свързва robo(k,2). От направените разсъждения за се определят следните действия за robo(k,2): 2S2S
a[k]=a[k+1]=1; print(k+1);
a[k]=2; print(k);
За рекурсивната стъпка:
Начинът, по който задачата се свежда до аналогична, но с по-малка размерност, т. е. свеждането на до и може да послужи като основа на следния извод за рекурсивната стъпка за robo(k,n): nS1−nS2−nS
a[k]=1;k++;robo(k,n-1);
a[k]=2;k++;robo(k,n-2);
Окончателно рекурсивната функция се оформя по следния начин:
void robo(int k,int n)
{
if(n==1){a[k]=1;print(k);}
else if(n==2)
{
a[k]=a[k+1]=1;print(k+1);
a[k]=2;print(k);
}
else
{
a[k]=1;k++;robo(k,n-1);
k–;
a[k]=2;k++;robo(k,n-2);}
}
Заключение
Така предложеният подход има предимството, че разбива поставената задача на подзадачи с градирана трудност. При решаването на поставения проблем обучаемия преминава през следните етапи:
- Определя се начина, по който задачата се свежда до еднотипна на дадената, но с по-малка размерност. Съществена роля тук се пада на определянето на характеристиката, даваща възможност за това.
- Получаване на рекурентна зависимост и начални условия.
- Съставяне на рекурсивния алгоритъм на базата на получената рекурентна зависимост.
- Реализация на съответната рекурсивна функция на изучавания език за програмиране.
Литература
[1] Наков П., Добриков П. Програмиране = + + Алгоритми; TopTeam Co., София, 2003 МАТЕМАТИКА, ИНФОРМАТИКА И КОМПЮТЪРНИ НАУКИ Велико Търново 2006 402
[2] Седжуик Р. Алгоритми на C, СофтПрес, София, 2004
[3] Тодорова, М. Програмиране на C++= ч.1, Сиела, София, 2003
[4] Johnsonbaugh R. Discrete Mathematics, Macmillan Publishing Company, New York, 1984
Сходни статии:
- Алгоритми АЛГОРИТМИ – ОСНОВНИ ПОНЯТИЯ Думата ’алгоритъм’ идва от името на арабския математик al-Khwarezmi, който през VIII в. описва откриването на десетичната бройна система и представя редица важни концепции в книгата...
- Програмиране от по-висок ред в C++ Функция, някои формални параметри на която са функции, се нарича функция от по-висок ред. В езика C++ е възможно формален параметър на функция да е указател към функция, а също...
- Програми за управление Осъществяване на закъснение Едночиповите микрокомпютри се използват обикновено за управление на някакви обекти. Аритметичните действия, които могат да извършват , се използват именно за целите на управлението, а не за...
- Програмиране в C и C++ Кодирането или съставянето на програмата е реализация на алгоритмите чрез език за програмиране. Езиците за програмиране от високо ниво, какъвто е и програмният език C, се характеризират със задължителни синтактични...
- Търсене на числа от поредица автор: Веселин Димитров Програмата е създадена с цел намирането на числа от поредица такива, които са по-големи от сбора на всички предхождащи го числа. Програмата позволява да се четат числа...