ch03-recursive.md

3 Ռեկուրսիվ ալգորիթմներ

3.1 Ներածություն

Օբյեկտը կոչվում է ռեկուրսիվ, եթե այն մասնակիորեն բաղկացած է կամ սահմանված է ինքն իրենով։ Ռեկուրսիան հանդիպում է ոչ միայն մաթեմատիկայում, այլև առօրյա կյանքում։ Ո՞չ չի տեսել ինքն իրեն պարունակող գովազդային պատկեր։

Նկ․ 3.1։ Ռեկուրսիա պարունակող նկար։

Ռեկուրսիայի հզորությունը մասնավորապես բացահայտվում է մաթեմատիկական սահմանումներում։ Ծանոթ օրինակներ են բնական թվերը, ծառաձև կառուցվածքները և որոշ ֆունկցիաներ․

1. Բնական թվեր․
   • 0-ն բնական թիվ է,
   • Բնական թվին հաջորդող թիվը նույնպես բնական թիվ է։
2. Ծառաձև կառուցվածքներ․
   • ∅-ը ծառ է (կոչվում է՝ դատարկ ծառ),
   • Եթե t_1-ը և t_2-ը ծառեր են, ապա t_1 և t_2 ժառանգներ պարունակողց ծառը նույնպես (բինար) ծառ է։
3. Ֆակտորիալ ֆունկցիան ― f(n)․
   • f(0) = 1
   • f(n) = n × f(n - 1) երբ n > 0։

Ակնհայտ է, որ ռեկուրսիայի հզորությունն ի հայտ է գալիս վերջավոր կանոններով օբյեկտների անվերջ բազմություն սահմանելիս։ Նույն կերպ անվերջ հաշվարկային քայլերը կարելի է նկարագրել վերջավոր գործողություններով ռեկուրսիվ ծրագրով, եթե նույնիսկ այդ ծրագիրը բացահայտ կրկնություններ չի պարունակում։ Սակայն ռեկուրսիվ ալգորիթմների կիրառումը տեղին է, եթե լուծվող խնդիրը, հաշվարկվող ֆունկցիան, կամ մշակվող տվյալների կառուցվածքները արդեն սահմանված են ռեկուրսիայի տերմիններով։ Ընդհանուր առմամբ P ռեկուրսիվ ծրագիրը կարող է արտահայտվել որպես հրահանգների S հաջորդականության (P֊ն չպարունակող) և հենց իր՝ P֊ի P կոմպոզիցիա։

P ≡ P[S, P]

Ռեկուրսիվ ծրագրերի նկարագրման անհրաժեշտ և բավարար գործիքը պրոցեդուրան կամ ենթածրագիրն է, քանի որ այն թույլ է տալիս հրամանին անուն տալ, որով էլ հետո այդ հրամաններին կարելի է դիմել։ ?? Եթե P պրոցեդուրան պարունակում է իր բացահայտ կիրառություն (կանչ), ապա ասում են, որ դա ուղղակի ռեկուրսիա է։ Եթե P֊ն պարունակում է մի այլ Q պրոցեդուրայի կանչ, որն էլ պարունակում է P֊ի (ուղղակի կամ անուղղակի) կանչ, ապա ասում են, որ P֊ում անուղղակի ռեկուրսիան է։ Այսինքն՝ ռեկուրսիայի առկայությունը կարող է և ակնհայտ չլինել ծրագրի տեքստից։

Սովորաբար պրոցեդուրայի հետ համապատասխանեցնում են լոկալ օբյեկտների բազմություն, դրանք կարող են լինել փոփոխականներ, հաստատուններ, տիպեր և պրոցեդուրաներ, որոնք, տրված պրոցեդուրայում լոկալ սահմանված լինելով, սահմանված չեն և իմաստ չունեն նրանից դուրս։ Այդպիսի պրոցեդուրայի ամեն մի ռեկուրսիվ ակտիվացիայի ժամանակ ստեղծվում է լոկալ օբյեկտների նոր բազմություն։ Չնայած որ դրանք ունեն նույն անուններն, ինչ պրոցեդուրայի նախորդ ակտիվացիայի լոկալ օբյեկտների բազմության համապատասխան տարրերը, դրանց արժեքները տարբեր են, իսկ անունների հետ կապված կոնֆլիկտները լուծվում են իդենտիֆիկատորների տեսանելիության տիրույթի կանոններով, այն է՝ իդենտիֆիկատորները միշտ հղվում են փոփոխականների վերջին ստեղծված բազմությանը։ ?? Նույն կանոնը ճիշտ է նաև պրոցեդուրաների պարամետրերի համար, որոնք, ըստ սահմանման, կապված են պրոցեդուրայի հետ։

Կրկնման հրամանների պես ռեկուրսիվ պրոցեդուրաներն էլ են չավարտվող հաշվարկների հնարավորություն ստեղծում, և այս պատճառով էլ պետք է հատուկ ուշադրություն հատկացնել հաշվարկների ավարտի խնդրին։ Ակնհայտ է, որ կա մի հաիմնական պահանջ՝ P պրոցեդուրայի ռեկուրսիվ կանչերը պետք է ենթարկվեն մի B պայմանի, որը ինչ որ պահի կդադարի ճշմարիտ լինելուց։ Այսպիսով, ռեկուրսիվ ալգորիթմների սխեման կարելի է ավելի ճշգրիտ արտահայտել հետևյալ բանաձևերից որևէ մեկով․

P ≡ IF B THEN P[S, P] END

P ≡ P[S, IF B THEN P END]

Կրկնությունների համար հաշվարկների ավարտվող լինելն ապացուցելու համար պետք է կատարել հետևյալ քայլերը․ ??

1. սահմանել f(x) ամբողջաթիվ ֆունկցիան (x-ը փոփոխականների բազմություն է) այնպիսին, որ f(x) < 0 արտահայտությունը ցույց տա հաշվարկների ավարտի պայմանը (որպես նախապայման կամ ետպայման),
2. կրկնության ամեն մի քայլում ապահովել f(x)-ի նվազելը։ f-ը կոչվում է կրկնության variant։

Նույն կերպ ռեկուրսիայի ավարտվող լինելը կարելի է ապացուցել՝ ցույց տալով, որ P պրոցեդուրայի կատարում նվազեցնում է մի ինչ-որ f(x) արժեք, և որ f(x) < 0 պայմանից բխում է ~B պայմանը։ Հաշվարկների ավարտը երաշխավորելու պարզ եղանակ է P պրոցեդուրայի հետ կապել մի (արժեքով փոխանցվող) պարամետր, ասենք n, և P պրոցեդուրան ռեկուրսիվ կանչել այդ պարամետրի n-1 արժեքով։ n > 0 արտահայտությունը B-ի փոխարեն տեղադրելը երաշխավորում է հաշվարկների ավարտը։ Ասվածը կարելի է արտահայտել ծրագրերի հետևյալ սխեմաներով․

P(n) ≡ IF n > 0 THEN P[S, P(n-1)] END

P(n) ≡ P[S, IF n > 0 THEN P(n-1) END]

Գործնական կիրառություններում պարտադիր պետք է ցույց տալ, որ ռեկուրսիայի ամբողջ խորությունը ոչ միայն վերջավոր է, այլ նաև շատ փոքր է։ Պատճառն այն է, որ P պրոցեդուրայի ամեն մի ռեկուրսիվ ակտիվացիայի ժամանակ նրա լոկալ փոփոխականների համար առանձնացվում է լրացուցիչ հիշողություն։ Ի լրումն այդ լոկալ փոփոխականների, պետք է պահպանել նաև հաշվարկների ընթացիկ վիճակը, որպեսզի P-ի նոր ակտիվացիայի ավարտից հետո հնարավոր լինի վերականգնել հինը։ QuickSort պրոցեդուրան մշակելու ժամանակ(Գլուխ 2) մենք արդեն հանդիպել ենք այս իրավիճակին։ Այնտեղ պարզվեց, որ եթե ծրագիրը կառուցվում է n տարրերը երկու մասերի բաժանող և այդ մասերի վրա կարգավորման երկու ռեկուրսիվ կանչեր կատարող պարզագույն հրամաններից, ապա ռեկուրսիայի խորությունը, վատագույն դեպքում, կարող է մոտենալ n-ի։ Իրավիճակի ավելի խելամիտ վերլուծությունը ցույց տվեց, որ խորությունը կարելի է սահմանափակել log(n) արժեքով։ n-ի և log(n)-ի տարբերությունը լրիվ բավարար է, որպեսզի ռեկուրսիայի համար խիստ անթույլատրելի դեպքը ձևափոխվի ռեկուրսիայի համար լրիվ թույլատրելի դեպքի։ ??

3.2 Երբ պետք չէ օգտագործել ռեկուրսիան

Ռեկուրսիվ ալգորիթմները հատկապես օգտագար են այն դեպքերում, երբ լուծվող խնդիրը կամ մշակվող տվյալները սահմանված են ռեկուրսիայի օգնությամբ։ Սա չի նշանակում սակայն, որ այդպիսի ռեկուրսիվ սահմանումները երաշխավորում են ռեկուրսիվ ալգորիթմների՝ խնդրի լուծման լավագույն ճանապարհը լինելը։ Իրականում, ռեկուրսիվ ալգորիթմները հենց այդպիսի անհաջող օրինակներով բացատրելն է դարձել ռեկուրսիան ծրագրավորման մեջ օգտագործելու դեմ լայն տարածում գտած նախապաշարմունքի գլխավոր պատճառը, երբեմն նաև ռեկուրսիան դարձնելով անարդյունավետության հոմանիշ։ ??

Ծրագրերը, որոնցում պետք է խուսափել ալգորիթմական ռեկուրսիայից, կարելի է բնութագրել դրանց կառուցվածքը բացատրող սխեմայով։ Այդ սխեմաները ցուցադրված են ստորև։ Հատկանշական է, որ սխեմայում հանդիպում է P-ի միայն մեկ կանչ՝ կառուցվածքի սկզբում կամ վերջում։

P ≡ IF B THEN S; P END

P ≡ S; IF B THEN P END

Այս սխեմաները ավելի բնական են այն դեպքերում, երբ հաշվարկվող արժեքները իրար հետ կապված են պարզ ռեկուրսիվ առնչություններով։ Դիտարկենք ֆակտորիալի լավ հայտնի օրինակը f_i = i!․

i = 0, 1, 2, 3, 4, 5, ...

f_i = 1, 1, 2, 6, 24, 120, ...

Առաջին թիվն ուղղակի սահմանված է որպես f_0 = 1, իսկ հաջորդ թվերը ռեկուրսիվ սահմանված են նախորդների միջոցով․

f_i+1 = (i+1) * f_i

Այս ռեկուրսիվ առնչությունից դուրս է բերվում n֊ի ֆակտորիալը հաշվելու ռեկուրսիվ ալգորիթմը։ Եթե ռեկուրսիայի i֊րդ մակարդակում i֊ի և f_i֊ի համար ներմուծենք համապատասխանաբար I և F նշանակումները, ապա կնկատենք, որ ֆակտորիալների հաջորդականության հաջորդ թվին անցնելու համար պետք է կատարել հետևյալ հաշվարկները․

I := I + 1; F := I * F

և վերը բերված սխեմայում S֊ի փոխարեն ներմուծելով այս երկու հրամանները, կստանանք ռեկուրսիվ ծրագիր․

P ≡ IF I < n THEN I := I + 1; F := I * F; P END

I := 0; F := 1; P

Մեր ծրագրավորման լեզվի նշանակումներով արտահայտված՝ առաջին տողը կունենա հետևյալ տեսքը․

PROCEDURE P;
BEGIN
  IF I < n THEN I := I + 1; F := I * F; P END
END P

Ավելի հաճախ օգտագործվում է ստորև բերված համարժեք տարբերակը։ P֊ն փոխարինվում է F ֆունկցիա֊ենթածրագրով, այսինքն՝ այնպիսի պրոցեդուրայով, որին բացահայտ համապատասխանեցված է հաշվարկվող արժեքը, և որն ուղղակիորեն կարելի է օգտագործել որպես արտահայտության բաղադրիչ։ Այս դեպքում արդեն F փոփոխական դառնում է ոչ պետքական, իսկ I փոփոխականի դերը կատարում է F ֆունկցիայի պարամետրը։

PROCEDURE F(I: INTEGER): INTEGER;
BEGIN
  IF I > 0 THEN RETURN I * F(I - 1) ELSE RETURN 1 END
END F

Հիմա արդեն պարզ է, որ այս օրինակում հեշտությամբ կարելի է ռեկուրսիան փոխարինել իտերացիայով։ Դա ցույց է տալիս հետևյալ ծրագիրը․

I := 0; F := 1;
WHILE I < n DO I := I + 1; F := I * F END

Ընդհանուր դեպքում ծրագրերը՝ կառուցված ըստ վերը բերված սխեմաների, պետք է ձևափոխել ըստ հետևյալ իտերատիվ սխեմայի․

P ≡ [x := x0; WHILE B DO S END]

Գոյություն ունեն էլ ավելի բարդ ռեկուրսիվ կառուցվածքի ծրագրեր, որոնք կարելի է և պետք է ձևափոխել իտերատիվ տեսքի։ Դրա օրինակ է Ֆիբոնաչիի թվերի հաշվարկումը, որոնք սահմանվում է այսպիսի անդրադարձ առնչությամբ․

fib_{n+1} = fib_n + fib_{n-1}

և fib_1 = 1, fib_0 = 0։ Այս բանաձևի ուղղակի և պարզ ծրագրավորումը հետևյալ ռեկուրսիվ պրոցեդուրան է․

PROCEDURE Fib(n: INTEGER): INTEGER;
  VAR res: INTEGER;
BEGIN
  IF n = 0 THEN res := 0
  ELSIF n = 1 THEN res := 1
  ELSE res := Fib(n-1) + Fib(n-2)
  END;
  RETURN res
END Fib

Fib(n) կանչով fib_n արժեքի հաշվելը բերում է այս ֆունկցիայի ռեկուրսիվ կանչերի։ Քանի՞ անգամ։ Նկատում ենք, որ n > 1 դեպքում ամեն մի կանչին հետևում է ևս երկու կանչ, այսինքն՝ կանչերի ընդհանուր քանակն էքսպոնենցիալ աչում է (տես նկ․ 3.2)։ Պարզ է, որ այսպիսի ծրագիրը գործնականում անպետք է։

Նկ․ 3.2։ Fib(5) կանչի 15 ակտիվացիաները։

Բարեբախտաբար Ֆիբոնաչիի թվերը կարող են հաշվարկվել իտերատիվ եղանակով, որը x = fib_i և y = fib_{i-1} լրացուցիչ փոփոխականների ներմուծմամբ թույլ է տալիս խուսափել կրկնվող արժեքների հաշվարկից։ ??

i := 1; x := 1; y := 0;

WHILE i < n DO z := x; x := x + y; y := z; i := i + 1 END

Նկատենք, որ x, y և z փոփոխականների վերագրումը կարելի է արտահայտել ընդամենը երկու վերագրումով՝ առանց z լրացուցիչ փոփոխականի․ x := x + y; y := x - y։

Այսպիսով եզրակացնում ենք, որ պետք է խուսափել ռեկուրսիայից, եթե կա ակնհայտ իտերատիվ լուծում։ Բայց սա չի նշանակում, որ պետք է ամեն գնով ազատվել ռեկուրսիայից։ Ինչպես ցույց կտրվի հետագա պարագրաֆներում և գլուխներում, կան ռեկուրսիայի շատ լավ կիրառություններ։ Այն փաստը, որ ըստ էության ոչ ռեկուրսիվ մեքենաների իրականացվում են ռեկուրսիվ պրոցեդուրաները, ցույց է տալիս, որ գործնական կիրառություններում ամեն մի ռեկուրսիվ ծրագիր կարելի է ձևափոխել համարժեք իտերատիվ ծրագրի։ Սակայն այդ դեպքում պետք կլինի բացահայտ մոդելավորել ու ղեկավարել ռեկուրսիայի ստեկը, իսկ այդ գործողությունները այնպես են մշուշում ծրագրի էությունը, որ դժվարանում է նրա բուն իմաստի ընկալումը։ ?? Եզրակացությունն այն է, որ իրենց բնույթով ռեկուրսիվ, այլ ոչ թե իտերատիվ, ալգորիթմները պետք է ձևակերպվեն որպես ռեկուրսիվ պրոցեդուրաներ։ Ասվածն ավելի լավ ընկալելու համար ընթերցողին առաջարկվում է համեմատել 2.3.3 բաժնում բերված QuickSort և NonRecursiveQuickSort ալգորիթմները։

Այս գլխի շարունակությունը նվիրված է մի քանի ռեկուրսիվ ծրագրերի մշակմանն այն իրավիճակներում, երբ ռեկուրսիայի կիրառման անհրաժեշտությունը լիովին արդարացված է։ Բացի այդ, 4-րդ գլխում ռեկուրսիան լայնորեն օգտագործվում է այն դեպքերում, երբ մշակվող տվյալների կառուցվածքները հնարավորություն են տալիս ակնհայտ ու բնական եղանակով կիրառել ռեկուրսիան։ ??

3.3 Ռեկուրսիվ ծրագրերի երկու օրինակ

Նկ․ 3.4-ում պատկերված գեղեցիկ գծագիրը բաղղկացած է հինգ կորերի վերադրումից։ Այդ կորերը համապատասխանում են մի այնպիսի կանոնավոր նմուշի, որ հնարավորություն է տալիս դրանք նկարել կոմպյուտերով ղեկավարվող դիսփլեյի կամ գծագրիչի վրա։ ?? Մեր նպատակն է դուրս բերել այն ռեկուրսիվ սխեման, որի օգնությամբ կարելի է կառուցել այդ նկարող ծրագրերը։ Զննելով նկ․ 3.4-ը տեսնում ենք, որ վերադրված կորերից երեքն ունեն նկ․ 3.3-ում պատկերված կորերի տեսքը․ դրանք նշանակենք H_1, H_2 և H_3։ Նկատում ենք, որ H_i+1 կորը ստացվում է H_i կորերի՝ երկու անգամ փոքր և համապատասխան անկյամբ պտտված չորս նմուշներից, որոնք իրար են կցված երեք ուղիղ գծիկներով։ Նկատենք նաև, որ H_1 կորը ստացվել է H_0 դատարկ (զրոյական) կորի չորս նմուշները երեք գծերով իրար միացնելով։ H_i կորը կոչվում է Հիլբերիտի i-րդ կարգի կոր՝ ի պատիվ դրանք հայտնաբերողի՝ մաթեմատիկոս Դ․ Հիլբերտի (D. Hilbert, 1891)։

Նկ․ 3.3։ Հիլբերտի 1-ին, 2-րդ և 3-րդ կարգի կորերը։

Քանի որ ամեն մի H_i կորը կազմված է չորս կիսով չափ փոքր H_i-1 կորերից, կարող ենք H_i կորը նկարող պրոցեդուրան արտահայտել որպես համապատասխան մասշտաբով և պտույտով չորս H_i-1 կորերը նկարող կանչերի համադրում։ ?? Դա ցուցադրելու համար H_i կորերի չորս մասերի տանք A, B, C և D անունները, իսկ կապակցող գծերը նկարող հրամաններն արտահայտենք համապատասխան ուղղությունն ունեցող սլաքներով։ ?? Այդ դեպքում կստանանք հետևյալ ռեկուրսիվ սխեմաները (նկ․ 3.3)․ ??

A: D ← A ↓ A → B
B: C ↑ B → B ↓ A 
C: B → C ↑ C ← D
D: A ↓ D ← D ↑ C

Ենքադրենք մեր տրամադրության տակ է հատվածներ նկարող line պրոցեդուրան, որը նկարող գրիչը տրված ուղղությամբ տեղափոխում է տրված հեռավորությամբ։ ?? Հարմարության համար ընդունենք, որ ուղղությունը տրվում է պրողեդուրայի i ամբողջաթիվ պարամետրով՝ որպես 45 × i աստիճան։ Եթե միավոր հատվածի երկարությունը նշանակենք u, ապա A տիպի կորը նկարող պրոցեդուրան կարելի է արտահայտել իր և համանման ձևով սահմանված B և D պրոցեդուրաների ռեկուրսիվ կանչերով։

PROCEDURE A (i: INTEGER);
BEGIN
  IF i > 0 THEN
    D(i-1); line(4, u);
    A(i-1); line(6, u);
    A(i-1); line(0, u);
    B(i-1)
  END
END A

This procedure is initiated by the main program once for every Hilbert curve to be superimposed. The main procedure determines the initial point of the curve, i.e., the initial coordinates of the pen denoted by x0 and y0, and the unit increment u. The square in which the curves are drawn is placed into the middle of the page with given width and height. These parameters as well as the drawing procedure line are taken from a module Draw. Note that this module retains the current position of the pen.

DEFINITION Draw;
  CONST width = 1024; height = 800;
  PROCEDURE Clear; (*clear drawing plane*)
  PROCEDURE SetPen(x, y: INTEGER);
  PROCEDURE line(dir, len: INTEGER);
    (*draw line of length len in direction dir*45
	  degrees; move pen accordingly*)
END Draw.