Рекурзија и итерација

Кога се обидуваме да решиме некој проблем со помош на компјутерска програма, се трудиме да го разделиме проблемот на помали делови, потпроблеми кои се полесни за решавање.  Кога потпроблемот е ист како и главниот, но на помало множество податоци, велиме дека проблемот е дефиниран рекурзивно.

латински: re = назад + currere = извршува;

Проблем : Отворање руски кукли (Матрјошки)

Замислете дека имате збир од кукли Матрјошки поставени една во друга, и барате златно прстенче што се наоѓа во најмалата кукла.

Базен случај (Услов за прекин): Ја отворате тековната кукла и проверувате дали внатре е прстенчето (или дали куклата е празна/нема повеќе кукли внатре). Ако ја најдете саканата кукла со прстенчето, застанувате и го земате.
Рекурзивен чекор: Ако куклата е празна но во неа има помала кукла, ја отворате помалата кукла и го повторувате истиот процес (се повикувате себеси за следната, помала кукла).

Дефиниција Рекурзија 

C ++ овозможува функцијата да се повикува самата себе си во рамките на сопствениот код. Тоа значи дека дефиницијата на функцијата има повик на функцијата према себе. Таквото повикување се нарекува повратно (анг. recurrent) повикување, односно повторување (анг. recursion) на повикувањето.

При секое самоповикување на функцијата натамошното извршување привремено се прекинува, освен при последното повикување кога целосно се извршува (тоа е граничниот случај). Потоа се продолжува секое прекинато извршување и тоа наназад. 

За да се овозможи завршување на функцијата  по секое прекинато извршување, потребно е да се паметат вредностите на сите променливи во моментот на прекинувањето, и тоа за сите прекини. Во рекурзивните потпрограми тоа се постигнува со користење на посебен дел од меморијата т.н. стек. Во него се ставаат вредностите на променливите при секој прекин., а при продолжување на извршувањето се вадат

Збирот на локални варијабли и параметри кои ги користи функцијата наново се креираат секогаш кога функцијата се себеповикува и се зачувуваат на врвот на стекот.

 
Заклучуваме: 

Доколоку една функција се повикува сама себе, тогаш тоа се нарекува рекурзивен повик, односно тој начин на повикување се нарекува рекурзија

За да се прекине рекурзијата во дефиницијата на функцијата мора да има израз со кој ќе се присили функцијата да се врати без давање рекурзивен повик кон себе. Отсуството на ваков услов ќе доведе до бесконечност на рекурзијата

Значи :

За да се избегне бесконечното извршување на подалгоритмот: 

 Мора да постои одреден критериум (краен критериум, граничен случај) за кој подалгоритмот не се повикува самиот себе.

  Секогаш кога подалгоритмот ќе се повика самиот себе мора да биде поблиску до крајниот критериум (граничен случај).
Клучни елементи на секоја рекурзија

Секое рекурзивно решение е составено од два главни делови или случаи

 Базен случај – условот кој ја запира рекурзијата. Без него, програмата ќе паѓа поради грешка од тип Stack Overflow (преполнување на стекот)

 Рекурзивен случај. Делот во кој функцијата се повикува себеси со променети (обично помали) аргументи, приближувајќи се кон базниот случај.

Рекурзивниот случај има три компоненти: 

o Раздели го проблемот на еден или повеќе поедноставни или помали делови на проблемот

 o Повикај ја функцијата (рекурзивно ) за секој дел, и

 o Комбинирај ги решенијата на деловите во решение на целиот проблем.

рекурзивна функција за пресметка на факториел

int factorial(int N)
{
if (N <= 1) //N==0 || N==1
return 1; //(0!)=1,(1!)=1, po definicija
else
return N * factorial(N-1);//rekurziven povik
}

Каква врска имаат рекурзијата и стекот?

Кога функција повикува друга функција, програмата мора да запомни каде треба да продолжи по завршувањето на повиканата функција.
За тоа се користи стекот на повикувања (call stack).
Кај рекурзијата, секое ново повикување создава нова рамка на стекот. Кога ќе се достигне базниот случај, повиците почнуваат да се враќаат наназад 

Стекот во C++ е линеарна структура на податоци што работи по принципот LIFO (Last In, First Out — последен влегол, прв излегува). Елементите се додаваат и се отстрануваат само од врвот на стекот

Поимите push и pop се двете основни операции (методи) со кои управуваме со податоците во структурата на податоци наречена стек (stack).

1. PUSH (Додавање елемент)
Што прави: Го става новиот елемент на самиот врв на стегот.
Како функционира во пракса: Исто како кога ќе земеш чинија и ќе ја ставиш најгоре на веќе постоечките чинии во кутијата. Тој нов елемент сега стапнува на врвот и прв ќе биде достапен.
Во програмирањето (рекурзијата): Секогаш кога функцијата ќе се повика самата себе, компјутерот прави push на новиот мемориски блок (Stack Frame) на системскиот стог.

2. POP (Отстранување елемент)
Што прави: Го отстранува и го враќа елементот што се наоѓа на самиот врв на стегот.
Како функционира во пракса: Исто како кога ја земаш најгорната чинија од кутијата за да ја користиш. Не можеш да ја извадиш таа од средината или од дното додека не ги тргнеш сите над неа.
Во програмирањето (рекурзијата): Кога рекурзивната функција ќе го стигне базниот случај (return), таа се брише од меморијата — компјутерот прави pop на тој мемориски блок и се враќа назад на претходната задача.

Клучна филозофија на стегот: LIFO
Стегот работи по принципот LIFO (Last In, First Out — Последен влегува, прв излегува). Оние елементи што последно сме ги ставиле (push), први мора да ги тргнеме (pop).

Дефиниција повторување

Итерација е постапка на извршување на низа инструкции се додека е исполнет претходно зададен услов. Изразот итерација вклучува иницијализација, споредување, извршување на наредби во самиот циклус и конечно ажурирање на контролната варијабла.
По ажурирањето на контролната варијабла, се повторува постапката се додека условот во итерацискиот израз е вистинит. 3 видови структури за повторување се "for", while, "do-while".

Итерацијата не користи стог за зачувување на варијаблите. Ова значи дека итерацискиот израз е побрз во однос на рекурзивниот израз. Отсуството на услов додедува до бесконечност на циклусот.

#include <iostream>

using namespace std;

int factorial1(int n)

{

int r = 1;

for (int i=2; i<=n; i++)

r = r*i;

return r;

}

int factorial2(int n)

{

if (n <= 1) //n==0 || n==1

return 1; //(0!)=1, (1!)=1

return n * factorial2(n-1); //rekurziven povik

}

int main()

{

cout << factorial1(5) << endl; //120

cout << factorial2(5) << endl; //120

return 0;

}

Пример 1

#include < iostream >

using namespace std;
int stepen(int x, int n)
{
if(n==1)
return 1;
else
return x*stepen(x,n-1) ;
}
int main() {
int XN,X,N;
cin >> X; cin >> N;
XN=stepen(X,N);
cout << XN << endl;
return 0;
}

Пример 2

#include <iostream>

using namespace std;

int stepen(int a,int n)

{

    if(n==0)

    return 1;

    else if(n==1)

    return a;

    else 

    return a*stepen(a,n-1);  

}

int main()

{ int a,n;

 cin >> a >> n;

 cout << stepen(a,n);

 return 0;

}

Пример 3

#include <iostream>

using namespace std;

int zbir (int n)

{  if(n==0) 

    return 0;

    else 

    return  zbir (n-1)+n;  }

int main()

{    int n;

   cin >> n;

   cout << zbir(n);

   return 0;

}

Што работат следниве програми 

Задачи

1.Дополни
#include <iostream>
using namespace std;
int faktoriel(int n) {
// 1. Базен случај (услов за прекин на рекурзијата)
if (n == 0 || n == 1) {
return ____________; // Ученикот го допишува точниот резултат
}
// 2. Рекурзивен чекор
return n * faktoriel(____________); // Ученикот ја менува вредноста во повикот
}
int main() {
int broj = 5;
cout << "Faktorielot e: " << faktoriel(broj) << endl;
return 0;
}

Што ќе се случи со меморијата ако се избрише целиот if услов (базниот случај)?
Колку пати ќе се повика функцијата faktoriel ако внесеме broj = 4?

2. Корегирај 

#include <iostream>

using namespace std;

// Задача: Да се пресмета збирот на броевите од n до 1 (пр. за 3: 3 + 2 + 1 = 6)

int presmetajZbir(int n) {

    if (n == 1) {

        return 1;

    }

    // ВНИМАНИЕ: !

    return n + presmetajZbir(n - 1);   }

int main() {

    cout << presmetajZbir(3);

    return 0;

}

3. Објасни 

#include <iostream>

using namespace std;

void odbrojuvanje(int n) {

    // Базен случај: кога ќе падне под или на 0, запираме

    if (n <= 0) {

        return;     }

    cout << n << " ";

    // Корекција: Го намалуваме бројот за да се движиме кон крајот

    odbrojuvanje(n - 1);   }

int main() {

    odbrojuvanje(3); // Ќе испечати: 3 2 1

    return 0;

}

Прашања

1. Што претставува базниот случај (base case) во една рекурзивна функција во C++?
- функција main
- почетна вредност ма променливата во for циклусот
- условот кој ја прекинува рекурзијата и спречува бесконечно повикување

2. Што се случува на меморискиот стек (call stack) кога функцијата е од тип void и има наредба return; без вредност?

= функцијата веднаш завршува и излегува од тековниот блок

- циклусот автоматски се рестартира од почеток 

- програмата јавува грешка бидејќи мора да врати цел број 

- се креира нов мемориски рамковен блок (Stack Frame)

3. Која е главната разлика во потрошувачката на меморија помеѓу итерацијата (for циклус) и рекурзијата?

- нема никаква разлика
- итерацијата користи константна меморија, додека рекурзијата зезема нов простор на стекот за

  секој повик
- рекурзијата троши помалку меморија бидејќи не користи променливи 

4. Што ќе се случи доколку во рекурзивна функција заборавиме да го смениме параметарот во рекурзивниот повик (пр. f(n) наместо f(n-1))?
- програмата ќе падне поради прелевање на стекот (stack overflow)
- програмата ќе заврши со вредност 0
- ќе се испечати само првиот член