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

Ահա ռեկուրենտ ալգորիթմների հիմնական միտքը․

$n!$n, ! հաշվելիս մենք լուծեցինք $n!$n, !-ը (սկզբնական խնդիրը)՝ հաշվելով ենթախնդրի արժեքը, այսինքն՝ հաշվելով ավելի փոքր թվի ֆակտորիալը՝ $(n-1)!$left parenthesis, n, minus, 1, right parenthesis, !-ը (նույն խնդրի ավելի փոքր տարբերակը), և դրա լուծումն օգտագործելով՝ գտանք $n!$n, !-ը։

Ռեկուրենտ ալգորիթմը կաշխատի այն դեպքում, երբ փոքր ենթախնդիրներն ամենավերջում հասնեն առաջնային դեպքի։ $n!$n, !-ը հաշվելիս ենթախնդիրները շարունակ փոքրանում են՝ վերջում հասնելով $0!$0, ! դեպքին։ Դու պետք է վստահ լինես, որ վերջում հասնելու ես առաջնային դեպքին։

Օրինակ՝ ի՞նչ կլինի, եթե մենք փորձենք ռեկուրենտ մեթոդով հաշվել բացասական թվի ֆակտորիալը։ $(-1)!$left parenthesis, minus, 1, right parenthesis, !-ը հաշվելու համար նախ և առաջ պետք է հաշվես $(-2)!$left parenthesis, minus, 2, right parenthesis, !-ը, որպեսզի գտնես $-1$minus, 1-ը։ Բայց $(-2)!$left parenthesis, minus, 2, right parenthesis, !-ը հաշվելու համար նախ և առաջ պետք է հաշվես $(-3)!$left parenthesis, minus, 3, right parenthesis, !-ը, որպեսզի գտնես $-2$minus, 2-ը։ Հետո պետք է հաշվես $(-3)!$left parenthesis, minus, 3, right parenthesis, !-ը և այսպես շարունակ։ Այո, թվերը փոքրանում են, բայց դրանք նաև հեռանում են առաջնային դեպքից, այսինքն՝ $0!$0, ! հաշվելուց։ Այսպես դու երբեք պատասխան չես ստանա։

Նույնիսկ եթե վստահ ես, որ $n$n-ի արժեքը բացասական չէ, դու ոչ մի պատասխան էլ չես ստանա, եթե ենթախնդիրներն անընդհատ չփոքրանան։ Ահա օրինակ։ Վերցնենք $n! = n \cdot (n-1)!$n, !, equals, n, dot, left parenthesis, n, minus, 1, right parenthesis, ! հավասարումը և երկու կողմը բաժանենք $n$n-ի՝ ստանալով $n! / n = (n-1)!$n, !, slash, n, equals, left parenthesis, n, minus, 1, right parenthesis, !։ Արի ստեղծենք նոր փոփոխական՝ $m$m և այն հավասարեցնենք $n+1$n, plus, 1-ին։ Քանի որ բանաձևը գործում է բոլոր դրական թվերի համար, արի $m$m գրենք $n$n-ի փոխարեն՝ $m! / m = (m-1)!$m, !, slash, m, equals, left parenthesis, m, minus, 1, right parenthesis, !։ Քանի որ $m = n+1$m, equals, n, plus, 1, կստանանք $(n+1)! / (n+1) = (n+1-1)!$left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis, equals, left parenthesis, n, plus, 1, minus, 1, right parenthesis, !։ Նորից հետ փոխելով ու նկատի ունենալով, որ $n+1-1 = n$n, plus, 1, minus, 1, equals, n՝ ստանում ենք $n! = (n+1)! / (n+1)$n, !, equals, left parenthesis, n, plus, 1, right parenthesis, !, slash, left parenthesis, n, plus, 1, right parenthesis։ Այս բանաձևով կարող ենք երթադրել, որ կկարողանանք հաշվել $n!$n, !-ը՝ սկզբում գտնելով $(n+1)!$left parenthesis, n, plus, 1, right parenthesis, !-ը և այն բաժանելով $n+1$n, plus, 1-ի։ Բայց $(n+1)!$left parenthesis, n, plus, 1, right parenthesis, !-ը հաշվելու համար պետք է գտնես $(n+2)!$left parenthesis, n, plus, 2, right parenthesis, !-ը, հետո՝ $(n+3)!$left parenthesis, n, plus, 3, right parenthesis, !-ը, և այսպես շարունակ։ Դու երբեք չես հասնի 0\ դեպքին։ Ինչո՞ւ։ Որովհետև ամեն ռեկուրենտ ենթախնդիրը հաշվում է նախորդից ավելի մեծ թվի արժեքը, ոչ թե ավելի փոքր։ Եթե $n$n-ը դրական է, դու այդպես երբեք չես հասնի առաջնային դեպքին՝ 0-ին։

Ռեկուրսիայի այս միտքը կարող ենք ներկայացնել երկու կանոնի տեսքով․

Նույնը պատկերացնենք ռուսական տիկնիկի՝ մատրյոշկայի օրինակով։ Չնայած դրանք որևէ ալգորիթմի հետ կապ չունեն, բայց յուրաքանչյուր տիկնիկ ծածկում է իրենից ավելի փոքր տիկնիկին (ճիշտ ռեկուրենտ ալգորիթմի նման) այնքան, մինչև ամենափոքրը չի ծածկում ոչ մի տիկնիկ (առաջնային դեպքի պես)։

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