Тарзи сохтани функсияҳоро мо дар дарсҳои пештара нишон дода будем. Функсияҳое, ки мо дар намунаҳо оварда будем, одатан аз қисми ибтидои барнома истифода ё ки даъват мешуданд (function calling). Мумкин аст, ки аз қисми ибтидои барнома ягон функсияи f1() даъват шавад, аз функсияи f1() ягон функсияи f2() даъват шавад ва ҳоказо. Агар функсия худро даъват кунад, он функсияи рекурсивӣ номида мешавад. Чунин тарзи рекурсия рекурсияи ошкор низ номида мешавад. Агар як функсия функсияи дигарро даъват кунад ва дар навбати худ функсияи дуввум функсияи якумро даъват кунад, ин функсияҳо низ рекурсивианд. Чунин тарзи рекурсия рекурсияи ноошкор номида мешавад. Аён аст, ки шаклҳои боз ҳам мураккабтари рекурсияи ноошкор имконпазиранд.
Фарз мекунем, ки барои ҳал намудани ягон масъала мо функсияи рекурсивӣ сохтанием. Дар ин дарс яке аз стратегияҳои машҳуртарини ҳал кардани масъала бо истифодаи функсияи рекурсивиро баён мекунем. Раванди ҳалли рекурсивии масъала ба давраҳо ҷудо карда мешавад. Дар қадами аввал барои ҳал намудани масъала функсияи рекурсивӣ даъват карда мешавад. Дар ин функсия масъала дар ҳолати соддатарин ҳал карда шудааст. Ҳолати соддатарини масъалаи додашуда масъалаи базисӣ номида мешавад. Агар функсия барои ҳал намудани масъалаи базисӣ истифода шуда бошад, функсия ҳал ё ки натиҷаро бозмегардонад. Агар функсия барои ҳал намудани масъалаи аз масъалаи базисӣ мураккабтар истифода шуда бошад, функсия ин масъаларо ба ду қисм ҷудо мекунад:
- қисми 1, ки онро функсия ҳал карда метавонад;
- қисми 2, ки онро функсия ҳал карда наметавонад.
Барои амали гардидани рекурсия қисми 2 бояд ба масъалаи ибтидоӣ монанд бошад, лекин нисбатан хурдтар ё соддатар. Азбаски масъалаи нави дар қисми 2 ҳосилшуда ба масъалаи ибтидоӣ монанд аст, функсия нусхаи нави худро даъват мекунад бо мақсади оғоз кардани кор аз болои масъалаи нав - ин амал даъвати рекурсивӣ ё ки қадами рекурсия номида мешавад.
Азбаски дар ҳар як даъвати рекурсивӣ функсия масъаларо ба ду қисм ҷудо мекунад, миқдори қадамҳои рекурсия хело зиёд шуданаш мумкин аст. Барои ба итмом расидани рекурсия функсияи рекурсивӣ пайдарпаии масъалаҳои хурдтареро, ки ба масъалаи базисӣ наздик мешаванд, бояд ҳосил кунад. Вақте ки дар ягон қадами рекурсия функсия масъалаи базисиро дарьёфт мекунад, ҳал ё ки натиҷаи масъалаи базисиро ба даъвати пешина (қадами пешинаи рекурсия) бозмегардонад. Дар ин даъват натиҷаи қабулшуда бо қисме, ки онро функсия ҳал карда метавонад муттаҳид карда шуда, натиҷаи навбати ба даъвати боз як қадам пештара бозгардонида мешавад, ва ҳоказо. Ҳамин тавр натиҷаи охирон бунёд карда мешавад, ки он ба ҷои даъвати ибтидоӣ (мумкин аст ба қисми ибтидои барнома) бозгардонида мешавад. Яъне барои имконпазир гаштани бозгашт функсияи рекурсивиро чунин сохтан лозим аст, ки ҳар як қадами рекурсия калимаи махсуси return-ро дарбар гирад.
Ҳамчун татбиқи ғояи баёншуда, якчанд барномаҳои рекурсивиро месозем.
Мисоли 1. Факториал. Факториали адади бутуни ғайриманфии n ба n*(n-1)*(n-2)*...2*1 баробар аст, ишорааш n!. Инчунин, қабул шудааст, ки 1!=1 ва 0!=1. Масалан, 7!=7*6*5*4*3*2*1=5040.
Барномаи итеративӣ (ғайрирекурсивӣ) барои ҳисоби факториал чунин аст:
<html>
<head>
<title>Факториал</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<body>
<h1>Хисоби факториал</h1>
<form action="factorial1.php" method="get">
<p>Адади натурали (n>=0): <input type="text" name="n" /></p>
<p><input type="submit" value="Хисоб"/></p>
</form>
<?php
if(!isset($_GET['n']) || ($n = $_GET['n'])=='') {
echo "Адади натуралиро ворид намоед!<br>";
exit;
}
$f=1;
for($i=$n;$i>=1;$i--)
$f*=$i;
echo "$n!=$f";
?>
</body>
</html>
Агар ишора кунем, ки 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).
Дар асоси формулаи рекурсивӣ барномаи рекурсивии масъалаи ҳисоби факториалро тартиб медиҳем:
<html>
<head>
<title>Факториал</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<body>
<h1>Хисоби факториал</h1>
<form action="factorial2.php" method="get">
<p>Адади натурали (n>=0): <input type="text" name="n" /></p>
<p><input type="submit" value="Хисоб"/></p>
</form>
<?php
if(!isset($_GET['n']) || ($n = $_GET['n'])=='') {
echo "Адади натуралиро ворид намоед!<br>";
exit;
}
$f=factorial($n);
echo "$n!=$f";
function factorial($i) {
if($i<2) return 1;
$k=$i*factorial($i-1);
return $k;
}
?>
</body>
</html>
Агар ба барнома адади 5-ро дохил кунем, барои ҳисоби 5! барнома тавре, ки дар расми поёни нишон дода шудааст, амал мекунад:
Ҳангоми аз қисми асосии барнома даъват шудани функсияи рекурсивии factorial(), аввал санҷида мешавад, ки адади ба он роҳишуда аз 2 хурд аст ё не. Агар адади қабулкардаи функсияи рекурсивӣ аз 2 хурд набошад (яъне масъала аз масъалаи базиси мураккабтар ё калонтар будааст), масъала ба ду қисм чудо карда мешавад:
- $k=$i* - қисми 1, ки онро функсия ҳал карда метавонад;
- factorial($n-1) - қисми 2, ки онро функсия ҳал карда наметавонад.
Ин кор то ба масъалаи базисӣ вохӯрдан, яъне то даъвати factorial(1), такрор меёбад. Агар адад аз 2 хурд бошад (1 ё 0), функсияи factorial() адади 1-ро бозмегардонад ($k=1), яъне масъалаи базисӣ ҳал карда мешавад. Агар ин функсияи factorial() аз factorial() пештар даъват шуда бошад, қимат ба factorial() бозгардонида мешавад. Дар ин ҷо қимати бозгардонидашуда k ба қимати қабулшуда n зарб карда мешавад ва ба k бахшида мешавад. Агар ин функсияи factorial() боз пештар аз factorial() даъват шуда бошад, кимати k ба factorial() бозгардонида мешавад, ва протсесси баёншуда такрор меёбад. Агар ин функсияи factorial() аз қисми асосии барнома даъват шуда бошад, қимати k ба он бозмегардад, натиҷа чоп мешавад, кори барнома ба итмом мерасад.
Мисоли 2. Паёдарпии Фибоначчи. Пайдарпаии ададҳои Фибоначчи
0,1,1,2,3,5,8,13,21,...
бо 0 ва 1 сар шуда, чунин хосият дорад, ки ҳар як аъзои минбаъдаи пайдарпаи худ суммаи ду аъзои пештара мебошад:
ai=ai-1+ai-2
Барномаи итеративӣ (ғайрирекурсивӣ) барои ҳисоби намудани n-то аъзои аввала чунин аст:
<html>
<head>
<title>Пайдарпаии Фибоначчи</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<body>
<form action="fibonacci1.php" method="get">
<p>Чандто аъзо лозим аст? (n>1): <input type="text" name="n" /></p>
<p><input type="submit" value="Ҳисоб"/></p>
</form>
<?php
if(!isset($_GET['n']) || ($n = $_GET['n'])=='') {
echo "Адади натуралиро ворид намоед!<br>";
exit;
}
$a1=0; $a2=1;
echo "$n-то аъзои аввали пайдарпаии Фибоначчи:<br>";
echo "$a1, $a2";
for($i=0;$i<$n-2;$i++) {
$a=$a1+$a2;
echo ", $a";
$a1=$a2;
$a2=$a;
}
?>
</body>
</html>
Агар аъзои n-уми пайдарпаии Фибоначчиро бо f(n) ишора кунем, формулаи рекурсивии ҳисоби ин аъзо чунин аст:
f(n)= f(n-2)+ f(n-1)
ва f(0)=0, f(1)=1.
Дар асоси формулаи рекурсивӣ барномаи рекурсивии масъалаи ёфтани аъзоҳои пайдарпаии Фибоначчиро тартиб медиҳем:
<html>
<head>
<title>Пайдарпаии Фибоначчи</title>
<meta http-equiv="content-type" content="text/html; charset=utf-8" />
</head>
<body>
<form action="fibonacci2.php" method="get">
<p>Чандто аъзо лозим аст? (n>1): <input type="text" name="n" /></p>
<p><input type="submit" value="Ҳисоб"/></p>
</form>
<?php
if(!isset($_GET['n']) || ($n = $_GET['n'])=='') {
echo "Адади натуралиро ворид намоед!<br>";
exit;
}
$a1=0; $a2=1;
echo "$n-то аъзои аввали пайдарпаии Фибоначчи:<br>";
for($i=0;$i<$n;$i++)
echo fibonacci($i),", ";
function fibonacci($n) {
if($n==0 || $n==1) return $n;
return fibonacci($n-2)+fibonacci($n-1);
}
?>
</body>
</html>
Даъвати якуми функсияи fibonacci() аз қисми асосии барнома рекурсивӣ нест, лекин ҳамаи даъватҳои минбаъдаи fibonacci() рекурсивианд. Дар ҳар даъват функсияи fibonacci() месанҷад, ки n ба 0 ё 1 баробар аст ё не (масъалаи базисӣ). Агар ҷавоб TRUE бошад, 0 ё 1 бозгардонида мешаванд. Ҳангоми n калон аз 1 будан, ҳар як қадами рекурсия ду даъвати рекурсивиро, ки назар ба масъалаи ибтидои соддатаранд, ба вуҷуд меорад. Дар расми поёни ҳисоб шудани аъзои 5-уми пайдарпаии Фибоначчи нишон дода шудааст, функсияи рекурсивӣ f():
Қайд кардан лозим аст, ки барои ҳисоб намудани ҳар як аъзои минбаъдаи пайдарпаи, миқдори даъватҳои зарурӣ дучанд мешавад. Масалан, барои ҳисоб кардани аъзои 10-ум тақрибан ҳазор даъват (210), барои ҳисоб кардани аъзои 20-ум тақрибан миллион даъват (220), барои ҳисоб кардани аъзои 30-ум тақрибан миллиард даъват (230) лозиманд. Дар методҳои ҳисобкунӣ чунин душвориҳо афзуншавии экспонентсиалӣ номида мешаванд, ки компютерҳои пурқувваттарини дунёро назди онҳо очизанд.
Методҳои рекурсивӣ ва итеративиро муқоиса мекунем.
Ҳам итератсия ва ҳам рекурсия ба сохтори идоракунанда такья мекунанд:
- итератсияҳо сохторҳои сиклиро истифода мебаранд;
- рекурсияҳо сохторҳои интихобро истифода мебаранд.
Ҳам итератсия ва ҳам рекурсия такроршавиро дар бар мегиранд:
- итератсияҳо такроршавиро ошкоро дар бар доранд;
- рекурсияҳо такроршавиро ба воситаи даъватҳои такрории функсияҳо ба амал меоранд.
Ҳам итератсия ва ҳам рекурсия шарти ба охир расидани такроршавиро доранд:
- итератсияҳо баъди вайрон шудани шарти давомёбии такроршавӣ ба итмом мерасанд;
- рекурсияҳо баъди дарёфтани масъалаи базисӣ ба итмом мерасанд.
Ҳам итератсия ва ҳам рекурсия ба итмоми худ тадриҷан, пай дар пай наздик мешаванд:
- дар итератсияҳо ягон ҳисобкунак тадриҷан, то вайрон шудани шарти давом додани такроршавӣ тағйир меёбад;
- дар рекурсияҳо то ба масъалаи базисӣ расидан раванди ба вуҷуд овардани пайдарпаии масъалаҳои соддатар нигоҳ дошта мешавад.
Ҳам итератсия ва ҳам рекурсия беохир шуда метавонанд:
- агар шарти давомёбии такроршавӣ ҳеҷ вақт вайрон нашавад, сикли итеративии беохир ҳосил мешавад;
- агар қадами рекурсия масъалаи ибтидоиро то ба масъалаи базиси расидан содда накунад, рекурсияи беохир ба амал меояд.
Рекурсияҳо аз камбудиҳо фориғ нестанд. Тарзи рекурсивии ҳалли масъала назар ба тарзи итеративӣ мумкин аст, ки вақт ва хотираи зиёдтареро талаб кунад. Ҳар як масъалаеро, ки ба тарзи рекурсивӣ ҳал карда шудааст, метавон ба тарзи итеративӣ ҳал намуд. Одатан тарзи рекурсивӣ беҳтар дониста мешавад, агар он табиати масъаларо оддитар инъикос кунад, яъне он нисбатан аёнтар ва барои таҳлилу таҳрир осонтар бошад. Ноаён будани тарзи итеративии ҳал боз як сабаби авлотар шуморидани тарзи рекурсивӣ шуданаш мумкин аст.
Масъалаи зеринро бо методи рекурсивӣ ҳал кунед.
Манораи Ханой. Дар тахтае се тир зада шудааст. Дар тири якум якчанд гирдаҳо (дискҳо)-и диаметрашон камшаванда чида шудаанд:
Гирдаҳоро ба ҳамин тартиб дар тири сеюм ҷойгир кардан лозим аст. Гирдаҳоро аз тир ба тир фақат яктогӣ кӯчонидан мумкин аст. Гирдаи калонро ба болои гирдаи хурд гузоштан мумкин нест.
САВОЛҲО БАРОИ МУСТАҲКАМКУНӢ
1. Рекурсия чист?
2. Мисолҳои татбиқи рекурсияро оред.
3. Фарқи рекурсияҳои ошкор ва ноошкорро бо мисолҳо фаҳмонида диҳед.
4. Мисолеро, ки ҳалли рекурсивии он аз итеративиаш осонтар аст оред.
