OOП рекурзивни функции
Функција која се повикува себеси е позната како рекурзивна функција. И, оваа техника е позната како рекурзија.
Работа со рекурзија во C ++
prefix rekurzija()
{
... .. ...
rekurzija();
... .. ...
}
int main()
{
... .. ...
rekurzija();
... .. ...
}Функцијата може да биде со било кој префикс зависно каков резултат враќа назад.На сликата подолу е прикажано како функционира рекурзивната функција, повикувајќи се одново и одново.
Повторувањето продолжува сè додека не се исполни некој услов.
За да се спречи бесконечна рекурзија, може да се користи наредба
if - else (или сличен пристап) каде што едната
гранка прави рекурзивен повик, а другата не.
Пример 1. Да се состави програм кој со рекурзивна функција пресметува збир на природните броеви од 1 до n.
#include <iostream>
using namespace std;
int zbir(int n)
{
if(n==0)
return
0;
else
return zbir(n-1)+n;
}
int main()
{
int n;
cout << "vnesi go n" << endl;
cin>>n;
cout<<"zbirot
e "<<zbir(n);
return
0;
}
Пример 2. Да се состави програм кој со рекурзивна функција пресметува степен на природен број
#include <iostream>
using namespace
std;
int stepen(int a, int n)
{
if (n==1)
{
return a;
}
else
return
a * stepen(a,
n-1);
}
int main()
{
int n,a;
cout<<"Vnesi osnova"<<endl;
cin>>a;
cout<<"Vnesi stepen"<<endl;
cin>>n;
cout<<"a na
stepen n e "<<stepen (a,n);
return 0;
}
Пример 3. Да се состави програм кој со рекурзивна функција пресметува факториел на природен број
#include <iostream>
using namespace std;
int faktoriel(int n)
{
if (n==1)
{
return 1;
}
else
{
return n * faktoriel(n-1);
}
}
int main()
{
int n;
cout<<"Vnesi broj"<<endl;
cin>>n;
cout<<"Faktoriel e "<<faktoriel(n);
return 0;
}
Пример 4. Да се состави програм кој со рекурзивна функција ги печати фибоначиевите броеви од 1 до n
#include <iostream>
using namespace std;
int fibonaci_niza(int broj)
{
if(broj==0)
{
return 1;
}
if (broj==1)
{
return 1;
}
return fibonaci_niza(broj-1) + fibonaci_niza(broj-2);
}
int main()
{
int n,i;
cout << "vnesi go n" << endl;
cin>>n;
for(i=0;i<=n;i++)
cout<<fibonaci_niza(i)<<" ";
return 0;
}
Пример 5. Да се состави програм кој со рекурзивна функција пресметува збир на цифрите на природен број n.
#include <iostream>
using namespace std;
int zbir(int n)
{
if (n<10)
return n;
else
return n%10+zbir(n/10);
}
int main()
{
int n;
cout << "vnesi go n" << endl;
cin>>n;
cout<<"zbirot na cifrite e "<<zbir(n);
return 0;
}
Пример 6. Да се состави програм кој со рекурзивна функција пресметува дали производите на цифрите на два цели броја се исти. Производ на цифри да се направи со рекурзија.
#include <iostream>
using namespace std;
int proizvod(int n)
{
if
(n<10)
return
n;
else
return n%10*proizvod(n/10);
}
int main()
{
int n,m,a1,a2;
cout << "vnesi go prviot broj" << endl;
cin>>n;
cout << "vnesi go vtoriot broj" << endl;
cin>>m;
a1=proizvod(n);
a2=proizvod(m);
if(a1==a2)
cout<<"da";
else
cout<<"ne";
return 0;
}
Пример 7. Да се состави програм кој со рекурзивна функција пресметува збир на цифрите на природен број n. Да се провери и испечати дали збирот е прост број (проверката дали бројот е прост да се направи со функција).
#include <iostream>
using namespace std;
int zbir(int n)
{
if (n<10)
return n;
else
return n%10+zbir(n/10);
}
void prost(int m)
{
int i, t=0;
for(i=2;i<=m/2;i++)
{
if (m%i==0)
{
t=1;
break;
}
}
if (t==0)
cout<<"brojot e prost";
else
cout<<"brojot ne e prost";
}
int main()
{
int n,k;
cout << "vnesi go n" << endl;
cin>>n;
k=zbir(n);
cout<<"zbirot na cifrite e "<<zbir(n)<<endl;
prost(k);
return 0;
}
Пример 8. Да се состави програм кој со рекурзивна функција пресметува збир на парните цифри на природен број n.
#include <iostream>
using namespace std;
int zbir(int n)
{
int k;
if (n==0)
return 0;
else
{
k=n%10;
if(k%2==0)
return k+zbir(n/10);
else
return 0+zbir(n/10);
}
}
int main()
{
int n;
cout << "vnesi go n" << endl;
cin>>n;
cout << "zbirot na parnite cifri e " <<zbir(n)<< endl;
return 0;
}
Пример 9. Да се состави програм кој со рекурзивна функција пресметува збир на непарните цифри на природен број n.
#include <iostream>
using namespace std;
int zbir(int n)
{
int k;
if (n==0)
return 0;
else
{
k=n%10;
if(k%2!=0)
return k+zbir(n/10);
else
return 0+zbir(n/10);
}
}
int main()
{
int n;
cout << "vnesi go n" << endl; cin>>n;
cout << "zbirot na neparnite cifri e " <<zbir(n)<< endl;
return 0;
}
Пример 10. Да се состави програм кој за внесен цел број ги печати само цифрите од бројот кои се помали од 5 и бројот на отпечатени цифри. Печатењето на цифрите на бројот помали од 5 да се реализира со рекурзивна функција.
#include <iostream>
using namespace std;
void rekurzija(int m, int b)
{
int c;
if(m==0)
{
cout<<endl;
cout<<"ima "<<b<<" cifri pomali od 5";
}
else
{
c=m%10;
if(c<5)
{
cout<<c<<" "; b++;
return rekurzija (m/10,b);
}
else
return rekurzija (m/10,b);
}
}
int main()
{
int m,i,b=0;
cout << "vnesi go m" << endl;
cin>>m;
rekurzija(m,b);
return 0;
}
Пример 11. Да се состави програм кој за n внесени цели броеви ги печати само цифрите од бројот кои се помали од 5 и бројот на отпечатени цифри за секој број. Печатењето на цифрите на бројот помали од 5 да се реализира со рекурзивна функција.
#include <iostream>
using namespace std;
int mali(int a)
{
if(a==0)
return 0;
int cifra=a%10;
if(cifra<5)
{
int b= 1 + mali(a/10);
cout<<cifra<<" ";
return b;
}
return 0 + mali(a/10);
}
int main()
{
int i,n;
cout<<"Vnesi go n"<<endl;
cin>>n;
for(i=1;i<=n;i++)
{
int broj;
cin>>broj;
cout<<"brojot "<<broj<<" ima "<<mali(broj)<<" cifri pomali od 5"<<endl; cout<<endl;
}
return 0;
}
Пример 12. Да се состави програм кој со рекурзивна функција пресметува НЗД на два два природни броја.
#include <iostream>
using namespace std;
void NZD(int &a, int &b)
{
int ost; ost=a%b;
if(ost!=0)
{
a=b;
b=ost;
NZD(a,b);
}
}
void zamena(int &a, int &b)
{
int pom=a;
a=b;
b=pom;
}
int main()
{
int m,n;
cout << "vnesi dva celi brja " << endl;
cin>>m>>n;
if(m<n)
zamena(m,n);
NZD(m,n);
cout<<"NZD e "<<m;
return 0;
}
Пример 13. Да се состави програм кој со рекурзија го наоѓа индексот на првиот член на низа а со n елементи кој има вредност х. Ако таков елемент нема да се испечати вредноста -1.
#include <iostream>
using namespace std;
int baraj(int a[], int n, int x, int i)
{
if(i>=n-1)
return -1;
if(a[i]==x)
return i;
return baraj(a,n,x,i+1);
}
int main()
{
int n,i,a[100],x;
cout << "vnesi go n" << endl;
cin>>n;
cout<<"vnesi gi elementite na nizata"<<endl;
for(i=0;i<n;i++)
cin>>a[i];
cout << "vnesi go x" << endl;
cin>>x;
cout<<"pozicijata e "<< baraj(a,n,x,0);
return 0;
}
Пример 14. Да се напише програма која со рекурзивна функција со која се одредува најмал елемент на низа со цели броеви.
#include <iostream>
using namespace std;
int baraj(int a[], int n, int m, int i)
{
if (i>=n)
return m;
else
{
if(a[i]<m)
m=a[i];
return baraj(a,n,m,i+1);
}
}
int main()
{
int n,i,a[100],m;
cout << "vnesi go n" << endl;
cin>>n;
cout<<"vnesi gi elementite na nizata"<<endl;
for(i=0;i<n;i++)
cin>>a[i];
m=a[0];
cout<<"najmal element e "<< baraj(a,n,m,0);
return 0;
}
Повеќето дефиниции за рекурзивна функција користат само константи. Тие не ја менуваат вредноста на која било променлива, откако променливата има вредност. Тоа може да биде изненадување за некој што се навикнал да користи циклуси. Како може да се постигне повторување ако никогаш не се променат никакви променливи? Одговорот на тоа прашање е едноставен. Бидејќи секој повик до функција создава нова рамка за таа функција, повторувањето може да создаде многу различни променливи. Варијацијата потребна за повторување не се постигнува со промена на вредноста на една променлива, туку со создавање на многу променливи со различни вредности.
Пример 15: Да се состави програм кој ќе го состави обратен стринг од стринг внесен од тастатура со употреба на рекурзија
#include <iostream>
using namespace std;
void obraten(const string& a); //deklaracija na funkcija
int main() {
string str;
cout << " Vnesete string " << endl;
getline(cin, str);
obraten(str); // povik na funkcija
return 0;
}
void obraten(const string & str)
{
int dolzina = str.size();
if(dolzina == 1) {
cout << str << endl;
}
else
{
cout << str[dolzina - 1];
obraten(str.substr(0, dolzina - 1));
}
}
Пример 16: Да се состави програм кој ќе најде дали стринг внесен од тастатура е палиндром со употреба на рекурзија
#include <iostream>
#include <string>
using namespace std;
bool Palindrom(string zbor, int dolna, int gorna)
{
if (dolna >= gorna)
return true;
if (zbor[dolna] != zbor[gorna])
return false;
return Palindrom(zbor, dolna + 1, gorna - 1);
}
int main()
{
string zbor;
cout << "Vnesete string za proverka dali e palindrom" << endl;
getline(cin, zbor);
int stringDolzina = zbor.length();
if (Palindrom(zbor, 0, stringDolzina - 1))
cout << zbor << " : e palindrom." << endl;
else
cout << zbor << " : ne e palindrom." << endl;
return 0;
}
Пример 17: Да се состави програм кој ќе најде должина на стринг внесен од тастатура со употреба на рекурзија
#include <iostream>
#include <string>
using namespace std;
int dolzina(char* str) {
if (*str == '\0')
return 0;
else
return 1 + dolzina(str + 1);
}
int main() {
char str[] = "OOP";
cout<<"Dolzinata na stringot e : "<<dolzina(str);
return 0;
}