5-8 Маъруза Рекурсия

Амалий машғулот 1. Рекурция

Ишдан мақсад: С# дастурлаш тилида рекурсив функциялар билан ишлаш, улардан фойдаланиш кўникмаларига эга бўлиш. Дастурда турли кўринишдаги ва қийинчиликдаги рекурсив функциялардан фойдалана олиш.
Масаланинг қўйилиши: Тингловчи вариант бўйича берилган масалани С# дастурлаш тилида ишлаши ва керакли натижа олиши лозим.
Ишни бажариш учун намуна
Лабиринтда йўлларни излаш - Мисол Бизга Н * М квадратлардан иборат, тўртбурчак шаклида лабиринт берилган. Ҳар бир квадрат кесишувчи ёки кесишмайдиган бўлади. (кириш)лабиринтга унинг чап бурчагиданкиради ва лабирентнинг пастки ўнг бурчакдаги чиқиш йўлига бориши лозим. (чиқиш ). Ҳар бир таваккалчи ҳар бурилишда юқорига, пастга, чапга ёки ўнгга бир ҳолатда ҳаракатланишига тўғри келади чунки лабиринт тўсиқлари тўғридан тўғри ташқарига чиқиб кетишига йўл қўймайди. Бир хил ҳолатда иккита кесишмани кесиб ўтиш мумкин емас.акс ҳолда таваккалчи бир неча бурилишни амалга оширгач яна олдин бўлган жойга қайтиб келади ва адашган ҳисобланади. Лабиринтнинг кириш қисмидан чиқишигача бўлган барча мумкин бўлган йўлларни акс еттирувчи компютер дастурини ёзинг.
Бу қайта такрорлаш йўли билан осон ечиладиган масалага оддий мисол, қайта такрорлаш билан йечим янада мураккаб ва қийинлашади. Масалани тасаввур қилиш ва йечимини топиш учун битта намуна сифатида лабиринтни чизайлик:

Бошланғич ҳолатдан охиригача топшириқнинг талабларига жавоб берувчи 3 та турли йўл мавжудлигини кўришингиз мумкин ( ҳаракат фақат кесувчи квадратларга мумкин).

Юқоридаги тасвирда 1 дан 14 гача бўлган белгиланган рақамлар орқали йўлакка мос бурилишларни кўрсатади.
Лабиринтдаги йўллар –рекурцив алгоритм
Бу масалани қандай йечишимиз мумкин? Лабиринтнинг охирига олиб борувчи йўлни излаш ҳолатини қуйидагидек такрорий жараён сифатида кўриб чиқишимиз мумкин:

• 
  Лабиринтдаги жорий ҳолат қатор ёки устун кўринишида бўлсин. Аввал бошланғич ҳолатдан бошлаймиз (0, 0).
  
• 
  Жорий ҳолат изланган ҳолат бўлса (Н-1, М-1), йўлни топган бўламиз ва уни чоп етишимиз керак. Агар ушбу ҳолат кесишмайдиган бўлса, биз орқага қайтамиз (уни босиб ўтиш мумкин емас).
  
• 
  Агар жорий ҳолат аллақачон юз берган бўлса, биз орқага қайтамиз (уни икки марта босиб ўтишга ҳақли емасмиз).
  
• 
  Акс ҳолда биз 4 та мумкин бўлган йўналишда ечим излаймиз.
  
• 
  Биз лабиринтдан чиқиш йўлини барча мумкин йўналишлардан боришга ҳаракатланиш орқали такрор (худди шу алгоритм билан) излаймиз:
  

• 
  Чап томондан: ҳолат (қатор, устун-1);
  
• 
  Чап томондан: ҳолат (қатор, устун-1);
  
• 
  Юқоридан: ҳолат (қатор-1, устун);
  
• 
  Ўнг томондан: ҳолат (қатор, устун+1);
  
• 
  Пастдан: ҳолат (қатор+1; устун).
  

Ушбу алгоритмик ечимни топиш учун биз қайта ўйлаймиз. Бизга “берилган ҳолатдан чиқиш йўлини топиш” масаласи берилган. Бу қуйидаги 4 та вазифаларни келтириб чиқаради:

• 
  Айни ҳолатдан чиқишгача чап томондан йўл излаш;
  
• 
  Айни ҳолатдан чиқишгача юқори томондан йўл излаш;
  
• 
  Айни ҳолатдан чиқишгача ўнг томондан йўл излаш;
  
• 
  Айни ҳолатдан чиқишгача паст томондан йўл излаш;
  

Биз ҳар бир мумкин бўлган ҳолатдан 4 та йўналишни текширамиз ва босиб ўтилган йўллардан ҳаракатланмаймиз, биз барибир йўлни топишимиз керак. Бу вақтда такрорланиш олдинги масалалардек оддий емас. ҳар бир қадамда биз чиқиш ёки тақиқланган ҳолатда еканлигимизни текширишимизга тўғри келади, шундан сўнг босиб ўтилган ҳолатни белгилашимиз ва такроран тўртта йўналишда изланишни давом еттиришимиз керак.
Такрорий ҳаракатлардан қайтгач, бошланғич нуқтани босиб ўтилмаган йўл сифатида белгилаб олиш лозим. Информатикада бундай секин ҳаракатланиш чекиниш орқали излаш деб юритилади.
static char[,] lab =
{
{' ', ' ', ' ', '*', ' ', ' ', ' '},
{'*', '*', ' ', '*', ' ', '*', ' '},
{' ', ' ', ' ', ' ', ' ', ' ', ' '},
{' ', '*', '*', '*', '*', '*', ' '},
{' ', ' ', ' ', ' ', ' ', ' ', 'e'},
};
static void FindPath(int row, int col)
{
if ((col < 0) || (row < 0) ||
(col >= lab.GetLength(1)) || (row >= lab.GetLength(0)))
{
// We are out of the labyrinth
return;
}
// Check if we have found the exit
if (lab[row, col] == 'e')
{
Console.WriteLine("Found the exit!");
}
if (lab[row, col] != ' ')
{
// The current cell is not free
return;
}
// Mark the current cell as visited
lab[row, col] = 's';
// Invoke recursion to explore all possible directions
FindPath(row, col - 1); // left
FindPath(row - 1, col); // up
FindPath(row, col + 1); // right
FindPath(row + 1, col); // down
// Mark back the current cell as free
lab[row, col] = ' ';
}

static void Main()

{
FindPath(0, 0);
}