If you're seeing this message, it means we're having trouble loading external resources on our website.

Եթե գտնվում ես վեբ զտիչի հետևում, խնդրում ենք համոզվել, որ *.kastatic.org և *.kasandbox.org տիրույթները հանված են արգելափակումից։

Հիմնական նյութ

Ռեկուրենտ ալգորիթմների հատկությունները

Ահա ռեկուրենտ ալգորիթմների հիմնական միտքը․
Խնդիրը լուծելու համար լուծիր ենթախնդիր, որը նույն խնդրի ավելի փոքր տարբերակն է, և ենթախնդրի լուծումն օգտագործելով՝ լուծիր խնդիրը։
n! հաշվելիս մենք լուծեցինք n!-ը (սկզբնական խնդիրը)՝ հաշվելով ենթախնդրի արժեքը, այսինքն՝ հաշվելով ավելի փոքր թվի ֆակտորիալը՝ (n1)!-ը (նույն խնդրի ավելի փոքր տարբերակը), և դրա լուծումն օգտագործելով՝ գտանք n!-ը։
Ռեկուրենտ ալգորիթմը կաշխատի այն դեպքում, երբ փոքր ենթախնդիրներն ամենավերջում հասնեն առաջնային դեպքի։ n!-ը հաշվելիս ենթախնդիրները շարունակ փոքրանում են՝ վերջում հասնելով 0! դեպքին։ Դու պետք է վստահ լինես, որ վերջում հասնելու ես առաջնային դեպքին։
Օրինակ՝ ի՞նչ կլինի, եթե մենք փորձենք ռեկուրենտ մեթոդով հաշվել բացասական թվի ֆակտորիալը։ (1)!-ը հաշվելու համար նախ և առաջ պետք է հաշվես (2)!-ը, որպեսզի գտնես 1-ը։ Բայց (2)!-ը հաշվելու համար նախ և առաջ պետք է հաշվես (3)!-ը, որպեսզի գտնես 2-ը։ Հետո պետք է հաշվես (3)!-ը և այսպես շարունակ։ Այո, թվերը փոքրանում են, բայց դրանք նաև հեռանում են առաջնային դեպքից, այսինքն՝ 0! հաշվելուց։ Այսպես դու երբեք պատասխան չես ստանա։
Նույնիսկ եթե վստահ ես, որ n-ի արժեքը բացասական չէ, դու ոչ մի պատասխան էլ չես ստանա, եթե ենթախնդիրներն անընդհատ չփոքրանան։ Ահա օրինակ։ Վերցնենք n!=n(n1)! հավասարումը և երկու կողմը բաժանենք n-ի՝ ստանալով n!/n=(n1)!։ Արի ստեղծենք նոր փոփոխական՝ m և այն հավասարեցնենք n+1-ին։ Քանի որ բանաձևը գործում է բոլոր դրական թվերի համար, արի m գրենք n-ի փոխարեն՝ m!/m=(m1)!։ Քանի որ m=n+1, կստանանք (n+1)!/(n+1)=(n+11)!։ Նորից հետ փոխելով ու նկատի ունենալով, որ n+11=n՝ ստանում ենք n!=(n+1)!/(n+1)։ Այս բանաձևով կարող ենք երթադրել, որ կկարողանանք հաշվել n!-ը՝ սկզբում գտնելով (n+1)!-ը և այն բաժանելով n+1-ի։ Բայց (n+1)!-ը հաշվելու համար պետք է գտնես (n+2)!-ը, հետո՝ (n+3)!-ը, և այսպես շարունակ։ Դու երբեք չես հասնի 0\ դեպքին։ Ինչո՞ւ։ Որովհետև ամեն ռեկուրենտ ենթախնդիրը հաշվում է նախորդից ավելի մեծ թվի արժեքը, ոչ թե ավելի փոքր։ Եթե n-ը դրական է, դու այդպես երբեք չես հասնի առաջնային դեպքին՝ 0-ին։
Ռեկուրսիայի այս միտքը կարող ենք ներկայացնել երկու կանոնի տեսքով․
  1. Ամեն հաջորդ ռեկուրենտ կանչը պետք է լինի ավելի փոքր արժեքի համար, այսինքն՝ լինի ավելի փոքր ենթախնդիր։
  2. Ռեկուրենտ կանչերն ինչ-որ պահի պետք է հասնեն առաջնային դեպքի, որը լուծվում է առանց ռեկուրսիայի։
Նույնը պատկերացնենք ռուսական տիկնիկի՝ մատրյոշկայի օրինակով։ Չնայած դրանք որևէ ալգորիթմի հետ կապ չունեն, բայց յուրաքանչյուր տիկնիկ ծածկում է իրենից ավելի փոքր տիկնիկին (ճիշտ ռեկուրենտ ալգորիթմի նման) այնքան, մինչև ամենափոքրը չի ծածկում ոչ մի տիկնիկ (առաջնային դեպքի պես)։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։

Ուզո՞ւմ ես միանալ խոսակցությանը։

Առայժմ հրապարակումներ չկան։
Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: