Ռեկուրսիա

Ռեկուրսիա (), մի բան, որը պարունակում է իրեն (նմանին), որակվում է ռեկուրսիվ (ինքնիրք), պարզ ռեկուրսիա։ Սա վերաբերվում է ինչպես օբյեկտներին (տվյալներին), այնպես էլ՝ գործողություններին (ալգորիթմներին)։ Օրինակ, ինքն իրեն պարունակող իմաստուն Ֆուկուրամայի ճապոնական խաղալիքը, նրա ռուսական տարբերակ հայտնի «մատրյոշկան», իրար մեջ դրվող զատիկի ձվերի կամ չինական տուփերի հավաքածուն։

Այս խաղալիքների իմաստը հենց ռեկուրսիվ, ինքնիրք լինելն է՝ ինքը պարունակում է իրեն, մատրյոշկայի մեջ էլի մատրյոշկան է։

Երբ տարբեր բաներ փոխադարձ պարունակում են իրար (նմանների), ապա որակվում են որպես բարդ ռեկուրսիվ (իրարք)։ Այնպես, ինչպես «Դրոսթի» անվանումով կակաոյի փոշու շատ հայտնի տուփի դեպքում, որի վրա պատկերված սկուտեղին դրված տուփի և բաժակի վրա պատկերված են էլի նույն տուփի և բաժակի պատկերները։

Ռեկուրսիա  
կամ ծանոթություն ու սեր առաջին իսկ հայացքից

Բերենք ռեկուրսիվ օբյեկտների օրինակներ.

Հայելին հայելու մեջ  

Դասական օրինակ է, երբ հայելին տեղադրված է մի այլ հայելու դիմաց կամ էլ նկարում ենք այն, ինչ նկարում ենք։

Փաստորեն պատկերի մեջ նկարվող պատկերն է, որի մեջ նկարվող պատկերի մեջ նկարվող պատկերն է, որի մեջ նկարվող պատկերի մեջ նկարվող պատկերի մեջ նկարվող պատկերն է, որի մեջ ....։ Նմանապես, եթե փորձեք բջջայինով լուսանկարել հայելու մեջ արտացոլված նույն բջջայինի պատկերը։

Մ․Կ․ Էշերի «Նկարող ձեռքեր» նկարում՝ ձախը նկարում է աջին, որը նկարում է աջը նկարող ձախին, որը նկարում է ձախը նկարող աջը նկարող ձախը նկարող աջին, որը նկարում է ...։ Էշերի նկարը իրար կուլ տված օձերի պատմության նման է։ Այս դեպքում էլ մի օձը կուլ է տվել մեկ ուրիշ օձի պոչի կողմից, որն էլ, հակառակի պես, կուլ է տվել հենց առաջինին նրա պոչի կողմից։ Ստացվում է, որ օձերը կուլ են տվել ոչ միայն իրարք, այլև՝ իքնիրք։ Ահա այդ օձերի ռեկուրսիվ ագահության արդյունքը վեջին նկարում։

Տերտերն ու իր շունը
Մանկուց ծանոթ հայտնի բանաստեղծությունը տերտերի ու իր շան դժբախտ սիրո մասին՝

Տերտերն ուներ մի լավ շուն։
Նա իր շանը շատ էր սիրում։
Մի օր շունը միս գողացավ,
Տերտերը վրան խիստ բարկացավ։
Քարով զարկեց՝ շունը սատկեց։
Տարավ թաղեց, վրան գրեց.–
Տերտերն ուներ մի լավ շուն
Նա իր շանը շատ էր սիրում
Մի օր շունը միս գողացավ
Տերտերը վրան խիստ բարկացավ
Քարով զարկեց՝ շունը սատկեց
Տարավ թաղեց, վրան գրեց.–
Տերտերն ուներ մի լավ շուն ...
Այս բանաստեղծության ցանկացած քառյակից հետո սկսվում է էլի նույն բանաստեղծությունը։

Հիմա ես գիտեմ, որ դու արդեն գիտես, թե ինչ բան է ռեկուրսիան։ Ես նաև գիտեմ, որ դու գիտես, որ ես գիտեմ, որ դու գիտես, որ ես գիտեմ, որ դու գիտես, ..., թե ինչ է ռեկուրսիան։

Ծառ, ճյուղ, տոհմածառ

Ծառը կամ ճյուղը նույնպես ռեկուրսիվ են։ Ճյուղի ամեն ոստից աճում են նոր ճյուղեր, որոնց ամեն մի ոստից ևս աճում են ճյուղեր, և այդպես շարունակ։

Ձևականորեն ծառերը կարող են տարբեր գրաֆիկական ներկայացում ունենալ՝ ինչպես բնական աճող ծառ հիշեցնող պատկերով, այնպես էլ հարմար ձևով հարթությունը կամ տարածությունը համաչափ լցված ոստերը միացնող գծերի տեսքով։

Մարդկության կողմից ամենահայտնի և լայնորեն կիրառվող ամենահին ռեկուրսիվ բանը դա տոհմածառն է։ Անունն արդեն իսկ հուշում է, որ սա տոհմի սերունդների ծառի ճյուղերով ներկայացնումն է։

Տեսեք, թե ինչպես է պատկերված Անգլիայի թագուհի Վիկտորիայի (1840-1901) և արքայազն Ալբերտի (1831-1888) տոհմածառը։

Ներկայացված են նրանց տոհմի 9-ը ճյուղերը (երեխաները), ամեն մի ճյուղի ճյուղավորումները (թոռները) և այդ ճյուղավորումների որոշ շարունակությունները (ծոռները)։ Անմիջապես ճյուղերին, ոստերում պատկերված են տոհմի անդամները, իսկ կից՝ ամուսինները։

Գեն։ Բոլոր բիոլոգիական գոյացությունները՝ բույսերն ու կենդանիները, իրենց մեջ պարունակում են մի բան, որում պահվում է տվյալ բիոլոգիական տեսակի ողջ նկարագիրը, իր պատճենը։ Դա գենն է։ Գենով է պայմանավորած տվյալ բիոլոգիական տեսակի բազմացումն ու շարունակական վերարտադրությունը։

Բոլոր բիոլոգիական գոյացությունները ռեկուրսիվ են։

Տոհմածառը (մի զույգի, ամուսինների) գենետիկ ծառի պարզ տեսակն է։ Մարդկային ցեղի (աֆրիկացի Ադամի ու Եվայի) տոհմածառը դա մարդկության գենետիկ ծառն է։

Բառարան

Ծառի տեսքով է ներկայացվում նաև բառարանը։ Օրինակ, դիտարկենք բառերի հետևյալ ցանկը.

ձևել, ղազ, քարտաշ, ագարակ, ձույլ, քարտարան, ալազան, ձևական, ղազան, ձու, ալագյազ, ագռա, ձեթ, քարտ, ձուկ, ագռավ, քար, ձոն, ղազախ, ձի, ալ։

Բառարանը կարող է ներկայացվել, օրինակ, հետևյալ ծառի տեսքով (ընդգծված քառակուսին ցանկի բառ է)։

Ուշադրություն դարձրեք, որ ծառը կառուցված է այնպես, որ եթե բառարանը կարդաք սլաքներով առաջինը ձախից սկզբունքով, ապա բառերը կդասավորվեն ըստ այբբենական կարգի.

ագարակ ագռա ագռավ ալ ալագյազ ալազան ձեթ ձեւական ձեւել ձի ձոն ձու  ձուկ ձույլ ձրի ղազ ղազախ ղազան քար քարտ քարտաշ քարտարան

Շղթայական կոտորակներ
Ստորև բերված շղթայական կոտորակները ռեկուրսիվ են

Իսկապես, առաջինի դեպքում, նշանակելով կոտորակը x-ով և նկատելով, որ արտահայտության առաջին կոտորակի հայտարարը (նշված է կարմիրով) նույն x-ն է,

կունենանք

Ստացվածը նույնպես ռեկուրսիվ է՝ x-ը ներկայացված է մի արտահայտությամբ, որը պարունակում է x-ը։ Սա մարդկային առումով ավելի հեշտ ընկալելի, հաճախ հանդիպող և պարզ տեսք ունի։ Կոտորակի, այն է x-ի արժեքը հավասար է (1+√5)/2։ Սա հանրահայտ ոսկե հատման ճշգրիտ արժեքն է, իսկ մոտավորապես՝ 1.61803398875։

Հակադարձ գործողությունները (1+√5)/2-ը ներկայացնում են որպես ռեկուրսիվ, այնուհետև՝ շղթայական կոտորակի տեսքով։ Տեսեք.

Այժմ հավասարության աջ մասի կոտորակի հայտարարում գրված x-ը կարող ենք փոխարինել հենց իրենով՝ ձախ մասում գտնվող x-ին վերագրվող և նորից ինքն իրեն պարունակող 1+1/x արտահայտությամբ

Շարունակաբար, ամեն նոր ստացված արտահայտությունում փոխարինելով x-ը 1+1/x կամ արդեն նոր ստացված արտահայտությամբ, կունենանք

Նույնը ավելի ընդհանուր դեպքում՝
 
Որտեղից և

Եւ հակառակը՝

Ռադիոտեխնիկական անվերջ, այն է՝ ռեկուրսիվ շղթաներ
Ստորև բերված են դիմադրությունների այդպիսի շղթաների երկու օրինակ։

Առաջինի դեպքում, եթե նշանակենք շղթայի դիմադրությունը Z-ով և նկատենք, որ շղթայի առաջին հատվածից հետո եղած շղթան դիմադրությունների էլի նույն անվերջ շղթան է 

կարող ենք փոխարինել այդ շարունակությունը հենց Z-ին հավասար դիմադրությամբ։ Արդյունքում կստանանք հասարակ միացման մի սխեմա, որի Z դիմադրությունը կներկայացվի հետևյալ բանաձևով

Եթե նշանակենք x = Z/R, ապա առաջին բանաձևը կարելի է ներկայացնել արդեն ծանոթ շղթայական կոտորակի տեսքով։ Իսկապես,

Երևի թե հիմա ավելի իմաստալից է հնչում «շղթայական կոտորակ» արտահայտությունը։

Հաջորդ, իրար մեջ ներդրված եռանկյուն միացումներով դիմադրությունների անվերջ շղթան կարելի է ներկայացնել երեք, եռանկյունաձև միացված Z դիմադրությունների համարժեք սխեմայով։

Ստացված եռանկյան գագաթների միջև դիմադրությունը հավասար է 2Z/3։ Քանի որ շղթայի ներսում էլի նույն շղթան է, ապա ներքին շղթան կարելի է փոխարինել եռանկյունաձև միացված Z դիմադրություններով։ Ստացված սխեմայի մեծ եռանկյան գագաթների միջև դիմադրությունը էլի 2Z/3 է, այնպես որ կարող ենք գրել
 
Բանաձևերը հատուկ բերված են այս տեսքով, որպեսզի հուշեն ստացման եղանակը (պետք է կիսվի կենտրոնում միացված Z դիմադրությունը և միացվեն համապոտենցիալ կետերը)։ Ի վերջո գագաթների միջև դիմադրության համար կստանանք 2Z/3 = 2R/√3 կամ Z = √3·R։

Ռեկուրսիվ կորեր 

Որպես օրինակ ներկայացնենք քառակուսուց ստացվող այդպիսի մի կոր։ Ակնառու լինելու համար քառակուսու կողմերը ներկայացնենք վեկտորներով (սլաքներով) և համարակալենք 1-4։ Այժմ ներկայացնենք քառակուսու 1-ին կողմը մյուս 1-4 կողմերի միջոցով՝ կցելով կողմերն իրար ինչ որ հերթականությամբ։ Ասենք 1→2→1→4→1 հերթականությամբ, որի պատկերը ներկայացված է հարակից նկարում։

Հիմա, 1-ին կողմի այս նոր ներկայացման բոլոր հատվածները նույնպես փոխարինենք 1→2→1→4→1 կողմերի հաջորդականությամբ, ինչպես պատկերված է ստորև բերված նկարում։

Ի վերջո, այս 2-րդ փոխարկումից հետո կստանանք հարակից պատկերը։ Նույն սկզբունքով, 3-րդ անգամ, ստացված պատկերում կատարենք նույն փոխարկումները։ Այս 3-րդ և 4-6-րդ կարգի փոխարկումների արդյունքները հաջորդիվ պատկերված են ստորև՝

Եթե մենք կատարենք նկարագրված գործողությունները քառակուսու բոլոր կողմերի հետ, ապա առաջին փոխարկումից հետո, 1-ին կարգում քառակուսին կներկայացվեր ստորև բերված տեսքով։ Այս պատկերի ամեն մի հատվածը նորից փոխարինելով տրված ներկայացումով, 2-րդ կարգում կստանանք հարակից պատկերը՝

3-6-րդ կարգի փոխարկումների արդյունքները հաջորդիվ բերված են ստորև՝

Սույն հոդվածում ներկայացված ռեկուրսիվ կորերը կառուցված են  Recursive Curve Maker ծրագրով, իսկ hաջորդիվ բերված են նաև այդ ծրագրով կառուցված որոշ կորերի պատկերները։ Եթե խոշորացնեք պատկերները 4-10 անգամ, ապա կտեսնեք այդ կորերի կառուցման բոլոր մանրամասները։
 
Հիլբերտի փակ կորի 1-8 կարգերը (գծագրության ցուցադրությունը՝ այս տեսագրությունում)

Սերպինսկու քառանիստ կորի 1-8 կարգերը

Սահմանային դեպքում, երբ կառուցման կարգը ձգտում է անվերջության, ստացվում են ռեկուրսիվ կորեր՝ ինքնիրք, որի ամեն մի մասը էլի ինքն է։ Տեսեք, թե սահմանային դեպքում ինչպիսին է Սերպինսկու եռանիստ ռեկուրսիվ կորը։

Ռեկուրսիան ծրագրային համակարգերում

Ֆրակտալ 

Ռեկուրսիվ բնույթի այս և նման պատկերները մոդայիկ անուն ունեն՝ ֆրակտալներ։ Ամենահայտնի ֆրակտալները ստեղծել և գովազդել է Մանդելբրոտը, որոնց մասին նույնիսկ ֆիլմեր են նկարահանվել։ Նկարում պատկերված ֆրակտալով կարող եք 10 րոպե ճանապարհորդել դիտելով այս ֆիլմը՝ ։ Այս պատկերների խոշորացման չափն արդեն հասել է 10-ի 288 աստիճանի (!)։

Ռեկուրսիան այլ ոլորտներում 

«Գտնված երազը» մուլտֆիլմում աղջնակը հայտնվում է պատից կախված նկարում, որտեղ անքուն ծերուկի տանը կախված է նկար, ուր ևս կարող է մտնել և ․․․։

Ռեկուրսիայի հնարքն իր ստեղծագործություններում շատ է օգտագործել Ռոբերտ Սահակյանցը։ Օրինակ, «Խոսող ձուկը» ֆիլմում Էխ-էխի ձևափոխումներն ու խոսող ձկան իրար ներառող պատասխանները տարատեսակ ռեկուրսիաների մի ողջ շարք են ներկայացնում։

Ռեկուրսիայի հաճախ հանդիպող սխալ օրինակներ 
կամ ռեկուրենտը միշտ չէ, որ ռեկուրսիվ է

Շատ դեպքերում ռեկուրսիվ օբյեկտները կարելի է ներկայացնել որպես գործողությունների կամ օբյեկտների այնպիսի հաջորդականություն, երբ հաջորդը ներկայացվում է նախորդի միջոցով։ Այդպիսի ներկայացումը կոչվում է ռեկուրենտ։ Շղթայական կոտորակների դեպքում, ասենք

նրա x արժեքը կարելի է հաշվել հաջորդական քայլերով, ներկայացնելով այն հետևյալ կերպ՝

xn+1 = 1 + 1/(1 + xn)

Սա շղթայական կոտորակի ռեկուրենտ, հաջորդական քայլերով ներկայացումն է։ Սահմանային անցման դեպքում, երբ xn → x և xn+1 → x, էլի ստանում ենք նախորդը՝

մի բան, որը պարունակում է ինքն իրեն և չի հանդիսանում նույնություն՝ x ≡ x։

Սակայն, միշտ չէ, որ ռեկուրենտ բանաձևը, օբյեկտի ռեկուրենտ, հաջորդական ներկայացումը համարժեք է ռեկուրսիվ ներկայացմանը։ Եթե սահմանային անցումով չի ստացվում ռեկուրսիվ օբյեկտ, ապա այն ռեկուրենտ էլ կմնա։

Օրինակ ֆակտորիալը՝ N! = 1·2·3·...N հաճախ ներկայացվում է որպես ռեկուրսիվ օբյեկտ։ Ֆակտորիալը հաշվելու (N+1)! = N!·(N+1) ռեկուրենտ բանաձևի աջ մասը դիտարկվում է որպես էլի ֆակտորիալ պարունակող արտահայտություն և, այդ իսկ պատճառով, ռեկուրսիվ։ Սակայն, հասկանալի է, որ սահմանային դեպքում ֆակտորիալը ռեկուրսիվ ներկայացում N! = F(N!) չունի, այն ինքն իրենով չի ներկայացվում։

Այս առումով պետք է ուշադիր լինել. եթե ռեկուրենտ ներկայացումը սահմանային անցումով չի դառնում ռեկուրսիվ ներկայացում, ապա այն ռեկուրսիվ օբյեկտի ռեկուրենտ ներկայացում չէ։ X = F(X) ռեկուրսիվ ներկայացումը շատ դեպքերում կարելի է ներկայացնել որպես Xn+1 = F(Xn) հաջորդականություն, ռեկուրենտ արտահայտություն։ Սակայն հակառակը, կամայական Xn+1 = F(Xn) ռեկուրենտ ներկայացում միշտ չէ, որ կարող է ներկայացվել որպես ռեկուրսիվ՝ X = F(X)։

Նրբություններ կան նաև ինքնին ռեկուրսիվ օբյեկտի, և նրա փուլային ներկայացումների արժեքների հետ կապված հարցերում։ Օրինակ, տոհմածառում ճյուղերը տարբեր են արժեքի, տարբեր մարդկանց ներկայացնելու իմաստով, սակայն ռեկուրսիվ է կառուցվածքային, ֆունկցիոնալ իմաստով։ «Մատրյոշկայի» մեջ եղած նման առարկան գուցե և նկարազարդված լինի որպես «իվանուշկա» կամ փիսիկի տեսք ունենա, սակայն կառուցվածքային, ֆունկցիոնալ առումով բոլորն էլ «մատրյոշկա» են (սեղմ արտապատկերումներ են)։

Ինչպես և բոլոր նախնական հասկացությունները, ռեկուրսիան նույնպես ճշգրիտ և լրիվ սահմանում չունի։ Այնպես, ինչպես բազմության կամ այլ նախնական հասկացություններ մաթեմատիկայում, ֆիզիկայում և լեզվում ընդհանրապես՝ քանզի սկզբունքորեն ոչ մի համակարգ չի կարող լրիվ լինել։ Բացատրական բառարանը չի կարող բացատրել (սահմանել) բոլոր հասկացությունները, քանի որ մի հասկացություն պետք է բացատրվի մի այլ, ուրիշ հասկացությունով, եթե դա մաթեմատիկական նույնություն (տաֆտոլոգիա) չէ (տես Գյոդելի թեորեմը լրիվության մասին)։

Ռեկուրսիան ծրագրավորման մեջ 
Բազմաթիվ ծրագրավորման ֆունկցիաներում և ալգորիթմներում ևս օգտագործվում է ռեկուրսիվ մեթոդը։ struct element_of_list
 {
   struct element_of_list *next; /* հաջորդ նույն տեսքն ունեցող ֆունկցիային անցնող կոդ */
   int data; /* Տվյալներ պարունակող փոփոխական */
 };

Գրականություն 
   Նիկլաուս Վիրտի այս գրքում արտակարգ շարադրված են ծրագրավորման հիմնարար հասկացությունները, մասնավորապես տվյալների կառուցվածքային ներկայացումը և կառուցվածքային տվյալների մշակման ալգորիթմները։ Օրինակները բերված են այդ պահին հեղինակի կողմից ստեղծված և մինչ այժմ էլ մեծ տարածում ունեցող ծրագրավորման Պասկալ լեզվով, որում և առաջին անգամ լիարժեք սկսեց օգտագործվել ռեկուրսիայի գաղափարը որպես տվյալների ներկայացման և ալգորիթմների իրականացման հիմնարար եղանակ։ Թարգմանված է բազմաթիվ լեզուներով և ծրագրավորման դասընթացի գրականության ցանկում մինչ այժմ էլ պարտադիր ընթերցանության գիրք է։
  
 
 

 
 
 - offers a treatment of corecursion. 
 
 
 
 
, first chapter on set theory.

Ծանոթագրություններ

Արտաքին հղումներ

 Recursion  - tutorial by Alan Gauld. 
 A Primer on Recursion- contains pointers to recursion in Formal Languages, Linguistics, Math and Computer Science. 
 Zip Files All The Way Down. 
Nevins, Andrew and David Pesetsky and Cilene Rodrigues. Evidence and Argumentation: A Reply to Everett (2009). Language 85.3: 671--681 (2009). 
 Fractals - Hunting the Hidden Dimension. PBS Nova video, 2008, 54։25|}. 

Ռեկուրսիա