Rekursiya

Рекурсия — Функсия ўзига ўзи тўғридан-тўғри ёки қандайдир восита орқали мурожаат қилиш жараёнига рекурсия дейилади ва бундай функсия рекурсив функсия деб аталади^[1]. Рекурсив функсия ўзини — ўзи чақиргани учун дастурчилар орасида қуйи олдин рекурсия нимаглигини тушуниш керак“ — Степҳен Ҳаwкинг^[2]. Рекурсия функсионал дастурлашнинг асосий элементларидан ҳисобланади. Рекурсия деярли ҳамма жойда ишлатилади. Баъзи масалаларнинг итератив ечими жуда ҳам узун бўлиб кетиши мумкин. Рекурсия эса кодни бир неча баробар қисқартириб бериши мумкин. Аксарият тузилмалар ва алгоритмларни рекурсиясиз тасаввур қилиб бўлмайди. Треэ, Грапҳ, Ҳеап, Қуиcк Сорт, Мерге Сорт, … Бу ро'йҳатни жуда узоқ давом эттириш мумкин. Айниқса, мураккаб тузилмалар бўлган Треэ ва Грапҳларда рекурсия ҳар қадамда учрайди.

Камчилиги

Рекурсия ҳар доим хотирадан қўшимча жой талаб қилади.
Рекурсив ечимда хато қилиш эҳтимоли юқори, чунки рекурсия жуда ҳам чалғитувчи.
Рекурсив ечимни хатосини топиш қийин.
Мураккаб алгоритмни ҳисоблаш қийин.

Алгоритми

Қутилар ичма-ич ихтиёрий жойлаштирилган, қайсидир қути ичида калит бор. Сиз калитни топиш алгоритмини тузишингиз керак

Рекурсияга қўйиш учун ушбу икки шартни ёзиб оламиз

Ишлаш шарти: Қути ичида ички қути чиқса, уни очиб кўр. Агар ички қутидан калит чиқмаса ташқи қутининг келган жойидан давом эт.
Тўхташ шарти: Қути ичидан калит топилса тўхта.

Дастури

Фибоначчи кетма кетлигининг н — ҳадини рекурсия қисм дастур орқали ҳисобловчи дастур

#инcлуде <иостреам.ҳ>
инт фиб(инт);
инт маин()
{
инт н;
cоут << "н="; cин >> н;
cоут << фиб(н) << эндл;
ретурн 0;
}
инт фиб(инт к)
{
иф (к == 0 || к == 1) ретурн 1;
элсе ретурн фиб(к - 1) + фиб(к - 2);
}

^[3].

Рекурсияга оид дастур

#инcлуде <биц/стдc++.ҳ>
усинг намеспаcе стд;
воид тоwер(инт н, чар соурcеПоле, чар дестинатионПоле, чар аухилиарйПоле)
{
иф(0 == н)
    ретурн;
тоwер(н - 1, соурcеПоле, аухилиарйПоле, дестинатионПоле);
cоут << "Дискни ко'чиринг "<< н << " дан " << соурcеПоле <<" га "<< дестинатионПоле << эндл;
тоwер(н - 1, аухилиарйПоле, дестинатионПоле,
    соурcеПоле);
}
инт маин()
{
    тоwер(3, 'С', 'Д', 'А');    
    ретурн 0;
}

^[4].

Рекурсив функсиянинг тўхташ чегараси бўлмаса, амаллар чексиз бажарилаверади, оқибатда дастур хатолик келтириб чиқаради.

Манбалар

[1] ҳттпс://www.техноман.уз/пост/рекурсия_-нима-учун-у-керак.ҳтмл

[2] ҳттпс://www.wисефамоусқуотес.cом/степҳен-ҳаwкинг-қуотес/то-ундерстанд-реcурсион-оне-муст-фирст-ундерстанд-реcурсион-1247188/

[3] ҳттпс://тами.уз/матнга_қаранг.пҳп?ид=1047

[4] ҳттпс://www.геэксфоргеэкс.орг/реcурсиве-фунcтионс/

[1]

[2]

[3]

[4]