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

Подробности
Обновлено 10.01.2011 17:57
Просмотров: 1145

Тарзи сохтани функсияхоро мо дар дарсхои пештара нишон дода будем. Функсияхое, ки мо дар намунахо оварда будем, одатан аз функсияи 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. Мисолеро, ки халли рекурсивии он аз итеративиаш осонтар аст оред.

Нравится

Дополнительная информация