Ռեկուրսիա (ինֆորմատիկա)
Ռակուրսիա, ծրագրավորման մեջ մեթոդ, որում խնդրի լուծումը կախված է նույն խնդրի ավելի փոքր նմուշների լուծումներից[1]։ Մոտեցումը կարող է կիրառվել խնդիրների տարբեր տիպերի համար, և կրկնարկումը համակարգչային գիտության մեջ կենտրոնական գաղափարներից մեկն է[2]։
"Կրկնարկման հզորությունը ակնհայտորեն ընկած է վերջավոր պնդումով օբյեկտների անվերջ բազմությունների սահմանման հավանականության վրա։ Նույն կերպ անվերջ քանակի հաշվարկումները կարող են բացատրվել վերջավոր կրկնարկման ծրագրով, նույնիսկ եթե ծրագիրը չի պարունակում բացահայտ կրկնողություններ"[3]:
Շատ ծրագրավորման լեզուներ օգտագործում են կրկնարկումը՝ թույլատրելով ֆունկցիային կանչել ինքն իրեն ծրագրի տեքստի մեջ։ Որոշ ֆունկցիոնալ ծրագրավորման լեզուներ չեն սահմանում որևէ ցիկլային կառույցներ, սակայն հիմնվում են բացառապես կրկնարկման վրա, որպեսզի կրկնելով կանչեն կոդը։ Հաշվողականության թեորեմը ապացուցում է, որ միայն կրկնարկվող լեզուները Թյուրինգ ամբողջական են։ Դրանք այնքան հաշվողականությամբ հզոր են, որքան Թյուրինգի ամբողջական հարկադրական լեզուները, որը նշանակում է՝ դրանք կարող են լուծել նույնատիպ խնդիրներ, ինչպես հարկադրական լեզուները, նույնիսկ առանց հարկադրական ղեկավարման կառույցների, ինչպիսիք են «while»-ը և «for»-ը։
Կրկնարկվող ֆունկցիաներ և ալգորիթմներ[խմբագրել | խմբագրել կոդը]
Ծրագրավորման մեջ հաճախ հանդիպող մարտավարությունն է բաժանել խնդիրը օրիգինալի տիպի ենթախնդիրների, լուծել այդ ենթախնդիրները և համակցել արդյունքերը։ Սա հաճախ կոչվում է բաժանման և նվաճման մեթոդ։ Համակցված փնտրման աղյուսակին, որը տեղադրում է ենթախնդիրների լուծումների արդյունքերը (բազմիցս դրանք լուծելուց խուսափելու և հաշվարկման ավելորդ ժամանակին հետևելու համար), այն կարող է կոչվել դինամիկ ծրագրավորում կամ մեմոիզացիա։
Կրկնարկվող ֆունկցիայի սահմանումն ունի մեկից ավելի սկզբնական դեպքեր, այսինքն՝ ներմուծումը(ները) ինչի համար ֆունկցիան արդյունք է տալիս թրիվիալորեն (առանց կրկնարկման), և մեկ կամ մի քանի կրկնարկվող դեպքեր, այսինքն՝ ներմուծումը(ները) ինչի համար ծրագիրը կրկնվում է, արդյունք է տալիս (կանչում ինքն իրեն)։ Օրինակ՝ ֆակտորիալի ֆունկցիան կարող է սահմանվել կրկնարկմամբ 0! = 1 և, բոլոր n > 0, n! = n(n − 1)! հավասարումներով։ Հավասարումներից ոչ մեկը ինքն իրենով չի կազմում ամբողջական սահմանում. առաջինը սկզբնական դեպք է, իսկ երկրորդը՝ կրկնարկման դեպք։ Քանի որ սկզբնական դեպքը քանդում է կրկնարկման շղթան, այն երբեմն կոչվում է «սահմանափակման դեպք»։
Կրկնարկման դեպքերի աշխատանքը կարելի է տեսնել որպես բարդ ներմուծումների պարզեցում։ Ինչպես հարկն է ձևավորված կրկնարկվող ֆունկցիայի մեջ, յուրաքանչյուր կանչի հետ, ներմուծման խնդիրը պետք է պարզեցվի այնպես, որ վերջնական հասնի սկզբնական դեպքին։ (Այն ֆունկցիաները, որոնք չեն սահմանափակվում նորմալ պայմաններում, օրինակ՝ համակարգի և սերվերի գործողությունները, բացառություն են)։ Սկզբնական դեպքը չգրելու կամ այն սխալ թեստավորելու դեպքում, կարող է առաջանալ անվերջ ցիկլ։
Որոշ ֆունկցիաների համար (օրինակ՝ որևէ մեկը, որը հաշվում է հաջորդականություններ e = 1/0! + 1/1! + 1/2! + 1/3! + ...)-ի համար, չկա բացահայտ սկզբնական դեպք կիրառված ներմուծվող տեղեկությամբ։ Դրանց համար մեկը կարող է ավելացնել պարամետր (այնպիսին, որ անդամների քանակը ավելացվի մեր հաջորդականության օրինակին), որպեսզի տա «կանգառի չափանիշ», որը կստեղծի սկզբնական դեպք։ Այդպիսի օրինակը ավելի բնականորեն մեկնաբանվում է համատեղ կրկնարկմամբ, որում հաջողակ անդամները արտածման մեջ մասնակի գումարներ են։ Դա կարող է փոխակերպվել կրկնարկման՝ օգտագործելով ինդեքսավորող պարամետր, որպեսզի ասենք "հաշվի՛ր n-րդ անդամը (n-րդ մասնակի գումարը)":
Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]
- ↑ Graham, Ronald; Donald Knuth; Oren Patashnik (1990). Concrete Mathematics. Chapter 1: Recurrent Problems. Արխիվացված է օրիգինալից 2020 թ․ նոյեմբերի 6-ին. Վերցված է 2016 թ․ սեպտեմբերի 23-ին.
- ↑ Epp, Susanna (1995). Discrete Mathematics with Applications (2nd ed.). էջ 427.
- ↑ Wirth, Niklaus (1976). Algorithms + Data Structures = Programs. Prentice-Hall. էջ 126.