Кога се обидуваме да решиме некој проблем со помош на компјутерска програма, се трудиме да го разделиме проблемот на помали делови, потпроблеми кои се полесни за решавање. Кога потпроблемот е ист како и главниот, но на помало множество податоци, велиме дека проблемот е дефиниран рекурзивно.
Рекурзија е дефинирање на некој поим преку самиот себе, односно во дефиницијата се вклучува и поимот кој се дефинира.
Употреба на рекурзијата: дефиниција на мaтематички функции, дефиниција на структури на податоци.
латински: re = назад + currere = извршува;
Проблем : Пронајди го патот до дома
Решение со рекурзија :
1. Ако си дома, остани во место
2. Инаку, направи еден чекор кон дома
3. Пронајди го патот до дома
Точката 3 во описот на проблемот е повик на истиот проблем од дефиницијата (Пронајди го патот до дома), но веќе е направен еден чекор кон дома и проблемот е поедноставен.
Генералниот алгоритм кој го решава проблемот со рекурзија се состои од
1. тривијален /граничен случај ( со кој се прекинува процесот на пресметка)
2. извршување на една акција која не води кон тривијалниот случај
3.рекурзивен повик
Дефиниција Рекурзија
C ++ овозможува функцијата да се повикува самата себе си во рамките на сопствениот код. Тоа значи дека дефиницијата на функцијата има повик на функцијата према себе. Таквото
повикување се нарекува повратно (анг. recurrent) повикување, односно повторување (анг. recursion)
на повикувањето.
При секое самоповикување на функцијата натамошното извршување привремено се прекинува,
освен при последното повикување кога целосно се извршува (тоа е граничниот случај). Потоа се
продолжува секое прекинато извршување и тоа наназад.
За да се овозможи завршување на функцијата по секое прекинато извршување, потребно е да се
паметат вредностите на сите променливи во моментот на прекинувањето, и тоа за сите прекини. Во
рекурзивните потпрограми тоа се постигнува со користење на посебен дел од меморијата т.н. стек.
Во него се ставаат вредностите на променливите при секој прекин., а при продолжување на
извршувањето се вадат
Збирот на локални варијабли и параметри кои ги користи функцијата наново се креираат секогаш кога функцијата се себеповикува и се зачувуваат на врвот на стекот.
Заклучуваме:
Доколоку една функција се повикува сама себе, тогаш тоа се нарекува рекурзивен повик, односно тој начин на повикување се нарекува рекурзија
За да се прекине рекурзијата во дефиницијата на функцијата мора да има израз со кој ќе се присили функцијата да се врати без давање рекурзивен повик кон себе. Отсуството на ваков услов ќе доведе до бесконечност на рекурзијата
Значи :
Значи :
За да се избегне бесконечното извршување на подалгоритмот:
Мора да постои одреден критериум (краен критериум, граничен случај) за кој подалгоритмот
не се повикува самиот себе.
Секогаш кога подалгоритмот ќе се повика самиот себе мора да биде поблиску до крајниот
критериум (граничен случај).
Секое рекурзивно решение е составено од два главни делови или случаи
Базен случај – во кој проблемот е доволно едноставен да биде решен директно, и
Рекурзивен случај.
Рекурзивниот случај има три компоненти:
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} |
Дефиниција повторување
Итерација е постапка на извршување на низа инструкции се додека е исполнет претходно зададен услов. Изразот итерација вклучува иницијализација, споредување, извршување на наредби во самиот циклус и конечно ажурирање на контролната варијабла.
По ажурирањето на контролната варијабла, се повторува постапката се додека условот во итерацискиот израз е вистинит. 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;
}
Што работат следниве програми
No comments:
Post a Comment