Рекурсия дар C++

Печать

Тарзи сохтани функсияҳоро мо дар дарсҳои пештара нишон дода будем. Функсияҳое, ки мо дар намунаҳо оварда будем, одатан аз функсияи main() истифода ё ки даъват мешуданд (function calling). Мумкин аст, ки аз функсияи main() ягон функсияи f1() даъват шавад, аз функсияи f1() ягон функсияи f2() даъват шавад ва ҳоказо. Агар функсия худро даъват кунад, он функсияи рекурсивӣ номида мешавад. Чунин тарзи рекурсия рекурсияи ошкор низ номида мешавад. Агар як функсия функсияи дигарро даъват кунад ва дар навбати худ функсияи дуввум функсияи якумро даъват кунад, ин функсияҳо низ рекурсивианд. Чунин тарзи рекурсия рекурсияи ноошкор номида мешавад. Аён аст, ки шаклҳои боз ҳам мураккабтари рекурсияи ноошкор имконпазиранд.

Фарз мекунем, ки барои ҳал намудани ягон масъала мо функсияи рекурсивӣ сохтанием. Дар ин дарс яке аз стратегияҳои машҳуртарини ҳал кардани масъала бо истифодаи функсияи рекурсивиро баён мекунем. Раванди ҳалли рекурсивии масъала ба давраҳо ҷудо карда мешавад. Дар қадами аввал барои ҳал намудани масъала функсияи рекурсивӣ даъват карда мешавад. Дар ин функсия масъала дар ҳолати соддатарин ҳал карда шудааст. Ҳолати соддатарини масъалаи додашуда масъалаи базисӣ номида мешавад. Агар функсия барои ҳал намудани масъалаи базиси истифода шуда бошад, функсия ҳал ё ки натиҷаро бозмегардонад. Агар функсия барои ҳал намудани масъалаи аз масъалаи базиси мураккабтар истифода шуда бошад, функсия ин масъаларо ба ду қисм ҷудо мекунад:
- қисми 1, ки онро функсия ҳал карда метавонад;
- қисми 2, ки онро функсия ҳал карда наметавонад.

Барои амали гардидани рекурсия қисми 2 бояд ба масъалаи ибтидоӣ монанд бошад, лекин нисбатан хурдтар ё соддатар. Азбаски масъалаи нави дар қисми 2 ҳосилшуда ба масъалаи ибтидоӣ монанд аст, функсия нусхаи нави худро даъват мекунад, бо мақсади оғоз кардани кор аз болои масъалаи нав - ин амал даъвати рекурсивӣ ё ки қадами рекурсия номида мешавад.

Азбаски дар ҳар як даъвати рекурсивӣ функсия масъаларо ба ду қисм ҷудо мекунад, миқдори қадамҳои рекурсия хело зиёд шуданаш мумкин аст. Барои ба итмом расидани рекурсия функсияи рекурсивӣ пайдарпаии масъалаҳои хурдтареро, ки ба масъалаи базисӣ наздик мешаванд, бояд ҳосил кунад. Вақте ки дар ягон қадами рекурсия функсия масъалаи базисиро дарьёфт мекунад, ҳал ё ки натиҷаи масъалаи базисиро ба даъвати пешина (қадами пешинаи рекурсия) бозмегардонад. Дар ин даъват натиҷаи қабулшуда бо қисме, ки онро функсия ҳал карда метавонад муттаҳид карда шуда, натиҷаи навбати ба даъвати боз як қадам пештара бозгардонида мешавад, ва ҳоказо. Ҳамин тавр натиҷаи охирон бунёд карда мешавад, ки он ба ҷои даъвати ибтидоӣ (мумкин аст ба main()) бозгардонида мешавад. Яъне барои имконпазир гаштани бозгашт функсияи рекурсивиро чунин сохтан лозим аст, ки ҳар як қадами рекурсия калимаи махсуси return-ро дарбар гирад.

Ҳамчун татбиқи ғояи баёншуда, якчанд барномаҳои рекурсивиро месозем.

Мисоли 1. Факториал. Факториали адади бутуни ғайриманфии n ба n*(n-1)*(n-2)*...2*1 баробар аст, ишорааш n!. Инчунин, қабул шудааст, ки 1!=1 ва 0!=1. Масалан, 7!=7*6*5*4*3*2*1=5040.

Барномаи итеративӣ (ғайрирекурсивӣ) барои ҳисоби факториал чунин аст:

//factorial01.cpp
#include <iostream>
using namespace std;
int main() {
unsigned long n,i,f=1;
cout<<"Adadi butun (n>=0):";
cin>>n;
for(i=n;i>=1;i--)
f*=i;
cout<<n<<"!="<<f<<endl;
return 0;
}

Агар ишора кунем, ки f(n)=n!. Пас,

f(n)=n!=n*(n-1)!=n*f(n-1),

яъне формулаи рекурсивии ҳисоби факториал чунин аст:

f(n)=n*f(n-1).

Масалан, f(5)=5*4*3*2*1=120 ва f(4)=4*3*2*1=24, f(5)=5*f(5-1).

Дар асоси формулаи рекурсивӣ барномаи рекурсивии масъалаи ҳисоби факториалро тартиб медиҳем:

//factorial02.cpp
using namespace std;
#include <iostream>
unsigned long f(unsigned long n) {
unsigned long k;
if(n<2) return 1;
k=n*f(n-1);
return k;
}
int main() {
unsigned long n;
cout<<"Adadi butun (n>=0):";
cin>>n;
cout<<n<<"!="<<f(n)<<endl;
return 0;
}

Агар ба барнома адади 5-ро дохил кунем, барои ҳисоби 5! барнома тавре, ки дар расми поёнӣ нишон дода шудааст, амал мекунад:

Азбаски ҳангоми афзудани адад қимати факториали адад тез меафзояд, мо аз намуди long ва калимаи махсуси unsigned, барои муайян кардани ададҳои бутуни калони ғайриманфӣ, истифода бурдем. Ҳангоми аз main() даъват шудани функсияи рекурсивии f(), аввал санҷида мешавад, ки адади ба он роҳишуда аз 2 хурд аст ё не. Агар адади қабулкардаи функсияи рекурсивӣ аз 2 хурд набошад (яъне масъала аз масъалаи базисӣ мураккабтар ё калонтар будааст), масъала ба ду қисм ҷудо карда мешавад:
1) k=n* - қисми 1, ки онро функсия ҳал карда метавонад;
2) f(n-1) - қисми 2, ки онро функсия ҳал карда наметавонад.

Ин кор то ба масъалаи базисӣ вохӯрдан, яъне то даъвати f(1), такрор меёбад. Агар адад аз 2 хурд бошад (1 ё 0), функсияи f() 1-ро бозмегардонад (k=1), яъне масъалаи базисӣ ҳал карда мешавад. Агар ин функсияи f() аз f() пештар даъват шуда бошад, қимат ба f() бозгардонида мешавад. Дар ин ҷо, қимати бозгардонидашуда k ба қимати қабулшуда n зарб карда мешавад ва ба k бахшида мешавад. Агар ин функсияи f() боз пештар аз f() даъват шуда бошад, қимати k ба f() бозгардонида мешавад, ва протсесси баёншуда такрор меёбад. Агар ин функсияи f() аз main() даъват шуда бошад, қимати k ба main() бозмегардад, натиҷа чоп мешавад, кори барнома ба итмом мерасад.

Мисоли 2. Паёдарпии Фибоначчи. Пайдарпаии ададҳои Фибоначчи

0,1,1,2,3,5,8,13,21,...

бо 0 ва 1 сар шуда, чунин хосият дорад, ки ҳар як аъзои минбаъдаи пайдарпаи худ суммаи ду аъзои пештара мебошад.

Барномаи итеративӣ (ғайрирекурсивӣ) барои ҳисоби намудани n-то аъзои аввала чунин аст:

//fibonacci01.cpp
using namespace std;
#include <iostream>
int main() {
unsigned long a1=0,a2=1,a;
int i,n;
cout<<"Paydarpaii Fibonacci"<<endl;
cout<<"Chandto a'zo lozim(n>1)? ";
cin>>n;
cout<<a1<<", "<<a2;
for(i=0;i<n;i++) {
a=a1+a2;
cout<<", "<<a;
a1=a2;
a2=a;
}
cout<<endl;
return 0;
}

Агар аъзои n-уми пайдарпаии Фибоначчиро бо f(n-1) ишора кунем, формулаи рекурсивии ҳисоби ин аъзо чунин аст:

f(n)= f(n-2)+ f(n-1)

ва f(0)=0, f(1)=1.

Дар асоси формулаи рекурсивӣ барномаи рекурсивии масъалаи ёфтани аъзоҳои пайдарпаии Фибоначчиро тартиб медиҳем:

//fibonacci02.cpp
using namespace std;
#include <iostream>
unsigned long fibonacci(int n) {
if(n==0 || n==1) return n;
return fibonacci(n-2)+fibonacci(n-1);
}
int main() {
int i, n;
cout<<"Paydarpaii Fibonacci"<<endl;
cout<<"Chandto a'zo lozim(n>0)? ";
cin>>n;
for(i=0;i<n;i++)
cout<<fibonacci(i)<<", ";
cout<<endl;
return 0;
}

Даъвати функсияи fibonacci() аз main() рекурсивӣ нест, лекин ҳамаи даъватҳои минбаъдаи fibonacci() рекурсивианд. Дар ҳар даъват функсияи fibonacci() месанҷад, ки n ба 0 ё 1 баробар аст ё не (масъалаи базисӣ). Агар ҷавоб TRUE бошад, 0 ё 1 бозгардонида мешаванд. Ҳангоми n калон аз 1 будан, ҳар як қадами рекурсия ду даъвати рекурсивиро, ки назар ба масъалаи ибтидоӣ соддатаранд, ба вуҷуд меорад. Дар расми поёнӣ ҳисоб шудани аъзои 5-уми пайдарпаии Фибоначчи нишон дода шудааст, функсияи рекурсивӣ f():

Як чизро қайд кардан лозим аст, ки барои ҳисоб намудани ҳар як аъзои минбаъдаи пайдарпаӣ, миқдори даъватҳои зарурӣ дучанд мешавад. Масалан, барои ҳисоб кардани аъзои 10-ум тақрибан ҳазор даъват (210), барои ҳисоб кардани аъзои 20-ум тақрибан миллион даъват (210), барои ҳисоб кардани аъзои 30-ум тақрибан миллиард даъват (230) лозиманд. Дар методҳои ҳисобкунӣ чунин душвориҳо афзуншавии экспонентсиали номида мешаванд, ки компутерҳои пурқувваттарини дунёро назди онҳо оҷизанд.

Методҳои рекурсивӣ ва итеративиро муқоиса мекунем.

Ҳам итератсия ва ҳам рекурсия ба сохтори идоракунанда такья мекунанд:

  • итератсияҳо сохторҳои сиклиро истифода мебаранд;

  • рекурсияҳо сохторҳои интихобро истифода мебаранд.

Ҳам итератсия ва ҳам рекурсия такроршавиро дар бар мегиранд:

  • итератсияҳо такроршавиро ошкоро дар бар доранд;

  • рекурсияҳо такроршавиро ба воситаи даъватҳои такрории функсияҳо ба амал меоранд.

Ҳам итератсия ва ҳам рекурсия шарти ба охир расидани такроршавиро доранд:

  • итератсияҳо баъди вайрон шудани шарти давомёбии такроршавӣ ба итмом мерасанд;

  • рекурсияҳо баъди дарёфтани масъалаи базисӣ ба итмом мерасанд.

Ҳам итератсия ва ҳам рекурсия ба итмоми худ тадриҷан, пай дар пай наздик мешаванд:

  • дар итератсияҳо ягон ҳисобкунак тадриҷан, то вайрон шудани шарти давом додани такроршавӣ тағйир меёбад;

  • дар рекурсияҳо то ба масъалаи базисӣ расидан протсесси ба вуҷуд овардани пайдарпаии масъалаҳои соддатар нигоҳ дошта мешавад.

Ҳам итератсия ва ҳам рекурсия беохир шуда метавонанд:

  • агар шарти давомёбии такроршавӣ ҳеҷ вақт вайрон нашавад, сикли итеративии беохир ҳосил мешавад;

  • агар қадами рекурсия масъалаи ибтидоиро то ба масъалаи базисӣ расидан содда накунад, рекурсияи беохир ба амал меояд.

Рекурсияҳо аз камбудиҳо фориғ нестанд. Тарзи рекурсивии ҳалли масъала назар ба тарзи итеративӣ мумкин аст, ки вақт ва хотираи зиёдтареро талаб кунад. Ҳар як масъалаеро, ки ба тарзи рекурсивӣ ҳал карда шудааст, метавон ба тарзи итеративӣ ҳал намуд. Одатан тарзи рекурсивӣ беҳтар дониста мешавад, агар он табиати масъаларо оддитар инъикос кунад, яъне он нисбатан аёнтар бошад ва барои таҳлилу таҳрир осонтар. Ноаён будани тарзи итеративии ҳал боз як сабаби авлотар шуморидани тарзи рекурсивӣ шуданаш мумкин аст.

Масъалаи зеринро бо методи рекурсивӣ ҳал кунед.

Манораҳои Ханой. Дар тахтае се тир зада шудааст. Дар тири якум якчанд гирдаҳо (дискҳо)-и диаметрашон камшаванда чида шудаанд:

Гирдаҳоро ба ҳамин тартиб дар тири сеюм ҷойгир кардан лозим аст. Гирдаҳоро аз тир ба тир фақат яктогӣ кӯчонидан мумкин аст. Гирдаи калонро ба болои гирдаи хурд гузоштан мумкин нест.

САВОЛҲО БАРОИ МУСТАҲКАМКУНӢ
1. Рекурсия чист?
2. Мисолҳои татбиқи рекурсияро оред.
3. Фарқи рекурсияҳои ошкор ва ноошкорро бо мисолҳо фаҳмонида диҳед.
4. Мисолеро, ки ҳалли рекурсивии он аз итеративиаш осонтар аст оред.

Комментарии   

 
0 #2 Allzoda Mirzoali 30.11.2016 14:41
:-* Раҳмат бародар барои маълумот
Цитировать
 
 
+4 #1 Абдусамад 24.05.2012 12:09
:D то что прочитал на этом сайте всё супер но извените ребята за критику тут не достаточно информации :sad:
надеюсь модераторы согласны со мной
Цитировать
 

Добавить комментарий


Защитный код
Обновить

Произведение «OFTOB.COM» публикуется на условиях лицензии Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Непортированная.