Ռեկուրսիա

Երբևէ ունեցե՞լ ես մատրյոշկաներ։ Խաղալիքն այնպիսին է, որ սկզբում դու միայն մի տիկնիկ ես տեսնում, որը մոտավորապես այսպիսի տեսք ունի․

Իսկ հետո հանում ես դրա վերին հատվածը, իսկ այնտեղ մեկ այլ՝ ավելի փոքր տիկնիկ է։

Կարող ես դուրս հանել այդ տիկնիկը, հանել վերին հատվածը և ներսում կտեսնես ավելի փոքր տիկնիկ․

Ու էլի․

Եվ այդպես շարունակ, մինչև գտնում ես ամենափոքր տիկնիկին, որը չի բացվում․

Մենք սկսեցինք մի տիկնիկից և բացահայտեցինք ավելի ու ավելի փոքր տիկնիկներ այնքան, մինչև հասանք ամենափոքրին։

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

Ռեկուրսիան բազում կիրառումներ ունի։ Այս հոդվածներում կտեսնենք, թե ինչպես կարող ենք ֆակտորիալ հաշվել, տեսնել, թե բառը պալինդրոմ է արդյոք, հաշվել թվի աստիճանները, գծել տարբեր պատկերներ և լուծել Հանոյի աշտարակների հայտնի խնդիրը։ Հետագայում ռեկուրսիան կօգտագործենք այլ խնդիրներ լուծելու համար, այդ թվում՝ տեսակավորման խնդիրներ։

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