Асосҳои C++/Рекурсия

---

Рекурсия

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

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

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

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

Хамчун татбики гояи баёншуда, якчанд программахои рекурсивиро месозем.

Мисоли 1

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

Программаи итеративи (ғайрирекурсиви)

Программаи итеративи (гайрирекурсиви) барои хисоби факториал чунин аст:

//factorial01

1. include <iostream.h>

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

1. include <iostream.h>

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! программа тавре, ки дар расми поёни нишон дода шудааст, амал мекунад: