Կրկնարկում (ծրագրավորում)

Վիքիպեդիայից՝ ազատ հանրագիտարանից
Jump to navigation Jump to search
Ծառը ստեղծված է օգտագործելով Լոգո ծրագրավորման լեզուն և հիմնվելով հիմնականում կրկնարկման վրա:

Կրկնարկում, ծրագրավորման մեջ մեթոդ, որում խնդրի լուծումը կախված է նույն խնդրի ավելի փոքր նմուշների լուծումներից[1]: Մոտեցումը կարող է կիրառվել խնդիրների տարբեր տիպերի համար, և կրկնարկումը համակարգչային գիտության մեջ կենտրոնական գաղափարներից մեկն է[2]:

"Կրկնարկման հզորությունը ակնհայտորեն ընկած է վերջավոր պնդումով օբյեկտների անվերջ բազմությունների սահմանման հավանականության վրա: Նույն կերպ անվերջ քանակի հաշվարկումները կարող են բացատրվել վերջավոր կրկնարկման ծրագրով, նույնիսկ եթե ծրագիրը չի պարունակում բացահայտ կրկնողություններ"[3]:

Շատ ծրագրավորման լեզուներ օգտագործում են կրկնարկումը՝ թույլատրելով ֆունկցիային կանչել ինքն իրեն ծրագրի տեքստի մեջ: Որոշ ֆունկցիոնալ ծրագրավորման լեզուներ չեն սահմանում որևէ ցիկլային կառույցներ, սակայն հիմնվում են բացառապես կրկնարկման վրա, որպեսզի կրկնելով կանչեն կոդը: Հաշվողականության թեորեմը ապացուցում է, որ միայն կրկնարկվող լեզուները Թյուրինգ ամբողջական են: Դրանք այնքան հաշվողականությամբ հզոր են, որքան Թյուրինգի ամբողջական հարկադրական լեզուները, որը նշանակում է՝ դրանք կարող են լուծել նույնատիպ խնդիրներ, ինչպես հարկադրական լեզուները, նույնիսկ առանց հարկադրական ղեկավարման կառույցների, ինչպիսիք են «while»-ը և «for»-ը:

Կրկնարկվող ֆունկցիաներ և ալգորիթմներ[խմբագրել | խմբագրել կոդը]

Ծրագրավորման մեջ հաճախ հանդիպող մարտավարությունն է բաժանել խնդիրը օրիգինալի տիպի ենթախնդիրների, լուծել այդ ենթախնդիրները և համակցել արդյունքերը: Սա հաճախ կոչվում է բաժանման և նվաճման մեթոդ: Համակցված փնտրման աղյուսակին, որը տեղադրում է ենթախնդիրների լուծումների արդյունքերը (բազմիցս դրանք լուծելուց խուսափելու և հաշվարկման ավելորդ ժամանակին հետևելու համար), այն կարող է կոչվել դինամիկ ծրագրավորում կամ մեմոիզացիա:

Կրկնարկվող ֆունկցիայի սահմանումն ունի մեկից ավելի սկզբնական դեպքեր, այսինքն՝ ներմուծումը(ները) ինչի համար ֆունկցիան արդյունք է տալիս թրիվիալորեն (առանց կրկնարկման), և մեկ կամ մի քանի կրկնարկվող դեպքեր, այսինքն՝ ներմուծումը(ները) ինչի համար ծրագիրը կրկնվում է, արդյունք է տալիս (կանչում ինքն իրեն): Օրինակ՝ ֆակտորիալի ֆունկցիան կարող է սահմանվել կրկնարկմամբ 0! = 1 և, բոլոր n > 0, n! = n(n − 1)! հավասարումներով: Հավասարումներից ոչ մեկը ինքն իրենով չի կազմում ամբողջական սահմանում. առաջինը սկզբնական դեպք է, իսկ երկրորդը՝ կրկնարկման դեպք: Քանի որ սկզբնական դեպքը քանդում է կրկնարկման շղթան, այն երբեմն կոչվում է «սահմանափակման դեպք»:

Կրկնարկման դեպքերի աշխատանքը կարելի է տեսնել որպես բարդ ներմուծումների պարզեցում: Ինչպես հարկն է ձևավորված կրկնարկվող ֆունկցիայի մեջ, յուրաքանչյուր կանչի հետ, ներմուծման խնդիրը պետք է պարզեցվի այնպես, որ վերջնական հասնի սկզբնական դեպքին: (Այն ֆունկցիաները, որոնք չեն սահմանափակվում նորմալ պայմաններում, օրինակ՝ համակարգի և սերվերի գործողությունները, բացառություն են): Սկզբնական դեպքը չգրելու կամ այն սխալ թեստավորելու դեպքում, կարող է առաջանալ անվերջ ցիկլ:

Որոշ ֆունկցիաների համար (օրինակ՝ որևէ մեկը, որը հաշվում է հաջորդականություններ e = 1/0! + 1/1! + 1/2! + 1/3! + ...)-ի համար, չկա բացահայտ սկզբնական դեպք կիրառված ներմուծվող տեղեկությամբ: Դրանց համար մեկը կարող է ավելացնել պարամետր (այնպիսին, որ անդամների քանակը ավելացվի մեր հաջորդականության օրինակին), որպեսզի տա «կանգառի չափանիշ», որը կստեղծի սկզբնական դեպք: Այդպիսի օրինակը ավելի բնականորեն մեկնաբանվում է համատեղ կրկնարկմամբ, որում հաջողակ անդամները արտածման մեջ մասնակի գումարներ են: Դա կարող է փոխակերպվել կրկնարկման՝ օգտագործելով ինդեքսավորող պարամետր, որպեսզի ասենք "հաշվի՛ր n-րդ անդամը (n-րդ մասնակի գումարը)":

Ծանոթագրություններ[խմբագրել | խմբագրել կոդը]

  1. Graham Ronald, Donald Knuth, Oren Patashnik (1990)։ Concrete Mathematics։ Chapter 1: Recurrent Problems 
  2. Epp Susanna (1995)։ Discrete Mathematics with Applications (2nd ed.)։ էջ 427 
  3. Wirth Niklaus (1976)։ Algorithms + Data Structures = Programs։ Prentice-Hall։ էջ 126