Цел: Запознаване с метода за създаване на ефективно по – рекурсия. Създаване и използване на рекурсивни функции при решаване на сложни задачи. Теоретична част

Итерация и рекурсия

Рекурсията е особен начин на самоповторение. Една функция е рекурсивна, ако в дефиницията й се съдържа обръщение към самата нея. Такава рекурсия се нарича “пряка”.

Ако една функция (Р) се обръща към друга функция (Q), а тя от своя страна се обръща към (P), се казва че съществува непряка рекурсия:

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

Примери за рекурсивно дефинирани функции:

Факториел:

F(n)=1, ako n=0

F(n)=n*F(n-1), ako n>0

Числа на Фибоначи:

Fib(n)=0, ako n=0

Fib(n)=1, n=1

Fib(n)=Fib(n-1)+Fib(n-2) , n>1

Първата функция може да се реализира по 2 начина: 1) чрез итерация; 2) чрез рекурсивна функция.

Рекурсивната функция за определяне на n-факториел има следната дефиниция:

int Fk(int n){

if (n==0) return 1;

else return n*Fk(n-1); }

Рекурсивната функция за определяне на n-тото число на Фибоначи има следната дефиниция:

int Fib(int n){

if (n==0) return 0;

else if (n==1) return 1;

else

На фиг.5.1. са дадени “разгънати “ резултатите от изпълнението на рекурсивната функция int Fk(int n) и реализацията на рекурсивните обръщения ( за n=4).

n=4 Fk=0

n=3 Fk=0

n=1 Fk=0

n=1 Fk=1

n=3 Fk=6

n=4 Fk=24

фиг.5.1.

Изчисляването на функцията “Факториел” може да стане и чрез цикъл, без използване на рекурсивна функция:

Fk=1 ;

for (i=1; i<=n; i++)

Този фрагмент отразява изчисляването на Fk(n) чрез един краен цикъл, който е напълно определен. Очевидно това итерационно решение дава по-бързо резултат, отколкото рекурсивното решение и трябва да се предпочита.

Рекурсията, като метод, най-често се демонстрира с програмните решения на класически задачи като : “Задача за Ханойските кули”; “Задача за обхождане на шахматна дъска с фигурата “кон”” и др. Тук са избрани задачите “Алгоритъм на Евклид за намиране на НГОД на две числа” и “Задача за ханойските кули”.

Задача 1: Намиране на най-голям общ делител на две числа

Задачата се дефинира така: Да се намери най-големият общ делител на две цели положителни числа, които да се делят на него без остатък.

Рекурсивната реализация на алгоритъма на Евклид, за намиране на най-големият общ делител на две цели положителни числа, се представя със следната рекурсивна функция:

int Ngod(int m, int n){

if (n==0) return m;

else return Ngod(n, m%n);

}

Задача 2: Ханойски кули

Най-често задачата се дефинира по сления начин: Дадени са три пилона (ляв, среден и десен). На левия пилон са подредени n-на брой дискове, най-отдолу е диска с най-голям диаметър, най-отгоре – с най-малък диаметър. Няма дискове с еднакъв диаметър и диск с по-малък диаметър лежи върху диск с по-голям диаметър. Да се подредят дисковете на десния пилон с използване на средния пилон като спомагателен, без да се наруши изискването, диск с по-малък диаметър да се поставя върху диск с по-голям диаметър и на трите пилона.

Задачата може да се сведе до следните две подзадачи, обединени в следващия алгоритъм:

Hanoy (n; ляв, среден, десен)

Преместването на n>1 диска може да се сведе до преместване на n-1 диска от ляв на среден пилон, след това до преместване на n-тия диск от ляв на десен пилон, след това преместване на n-1 диска от среден на десен пилон.

Алгоритъмът добива следния вид:

void Hanoy (int n, pilon l, s, d) {

if (n==1) mestene (l, d))

else {Hanoy (n-1, l, d, s);

mestene (l, d);

Hanoy (n-1, s, l, d); }

}

Друго решение е предложено от Р.Седжуик в [7]. То e следното:

if (n==0) return;

Hanoy(n-1, -d);

shift(n,d);

Hanoy(n-1, -d);

}

Този сорс-код определя кой диск да бъде преместен и в коя посока: + означава един пилон надясно,прескачайки циклично към най-лявия пилон, тръгвайки от най-десния пилон; - означава един пилон наляво, също прескачайки циклично към най-десния пилон, ако се тръгне от най-левия пилон.

Бр.прем.(0) = 0

Бр.прем.(n)=2*Бр.прем.(n-1) – 1, за n>0

се получава за сложността на алгоритъма, с използване на основната операция “преместване на диск” (това е оценка за сложност по време, изразена чрез броя на преместванията):

Т прем.(n) = 2^n-1

Това означава, че за 5 диска са необходими 2^5-1 = 31 преметсвания, за 8 диска - 2^8-1 = 127 премествания и т.нат.

Едно примерно изпълнение на програма, решаваща тази задача, би могло да извежда резултат като следния, например:

Ханойски кули

Въведете броя дискове: 4

Премести диск от 1 пилон на 2 пилон

Премести диск от 1 пилон на 3 пилон

Премести диск от 2 пилон на 3 пилон

Премести диск от 1 пилон на 2 пилон

Премести диск от 3 пилон на 1 пилон

Премести диск от 3 пилон на 2 пилон

Премести диск от 1 пилон на 2 пилон

Премести диск от 1 пилон на 3 пилон

Премести диск от 2 пилон на 3 пилон

Премести диск от 2 пилон на 1 пилон

Премести диск от 3 пилон на 1 пилон

Премести диск от 2 пилон на 3 пилон

Премести диск от 1 пилон на 2 пилон

Премести диск от 1 пилон на 3 пилон

Премести диск от 2 пилон на 3 пилон

Край
Въпроси по темата и задачи за изпълнение:

1. Да се напише и експериментира програма, която определя и извежда НГОД на две цели положителни числа, въведени от клавиатурата.