Ալգորիթմներ և Տվյալների Կառուցվածքներ

Ռեկուրսիա

Ծրագրեր գրելիս հաճախ կանչում ենք տարբեր ֆունկցիաներ, որպեսզի կատարենք որոշակի, հստակ գործողություններ։ Օրինակ, sqrt-ն կանչում ենք, որպեսզի ստանանք թվի քառակուսի արմատը, կամ max/min ֆունկցիաները, որպեսզի գտնենք առավելագույն/նվազագույն արժեքներն ինչ-որ թվերի հավաքածուից։ Ռեկուրսիան այն գործընթացն է, երբ նույն ֆունկցիան կանչում է ինքն իրեն։ Այսինքն, եթե սահմանել ենք f անունով ֆունկցիա, և դրա մարմնում որևէ տեղ նորից կանչում ենք նույն f-ը (սովորաբար տարբեր արգումենտներով), ապա դա կլինի ռեկուրսիվ կանչ։
def f(n):                                   # f անունով ֆունկցիայի սահմանում
    print(f'f() called with argument {n}')  # Յուրաքանչյուր կանչի դեպքում տպում ենք (ցուցադրության համար)
    if n <= 0:                              # Դադարեցնենք, եթե n-ը բացասական է
        print('Let\'s stop here...')
    else:                                   # Հակառակ դեպքում կանչենք f ավելի փոքր թվով
        f(n - 1)

f(10)
Ահա թե ինչ կտպի ծրագիրը.
f() called with argument 10
f() called with argument 9
f() called with argument 8
f() called with argument 7
f() called with argument 6
f() called with argument 5
f() called with argument 4
f() called with argument 3
f() called with argument 2
f() called with argument 1
f() called with argument 0
Let's stop here...
Սա փոքր օրինակ է, որը ցույց է տալիս, թե ինչպես կարելի է գրել շատ պարզ ռեկուրսիվ ֆունկցիա։ Գործնական իրավիճակներում սովորաբար ֆունկցիաները ինչ-որ հաշվարկներ են կատարում և վերադարձնում արդյունքը՝ համեմատաբար աննշան տպումների փոխարեն։
Ալգորիթմական խնդիրներում ռեկուրսիան կարող է շատ օգտակար լինել, հատկապես գրաֆերի, avancerած տեսակավորման (սորտավորման) ալգորիթմների կամ backtracking-ի դեպքում, որոնք մենք կքննենք ավելի ուշ։ Ռեկուրսիվ խնդիրները բավականին տարածված են, և երբեմն ռեկուրսիվ լուծումը գրելն ավելի հեշտ է, քան ցիկլերով (iterative) տարբերակը։
Video preview
Տեսանյութ Reducible-ից — 5 Simple Steps for Solving Any Recursive Problem
Մեծ խնդիրները փոքր հատվածների բաժանելու և ամենափոքր/հեշտ տարբերակին հասնելու գաղափարը լավագույնս կարելի է հասկանալ «ռեկուրսիվ վստահության թռիչք» անվանմամբ հասկացությամբ։

Ռեկուրսիվ վստահության թռիչք

Ռեկուրսիվ լուծում իրականացնելիս, սովորաբար սահմանում են մի ֆունկցիա, որը որոշ փուլում իրեն ինքն իրեն է կանչում։ Այդ կոչվող մասը հենց ռեկուրսիվ կանչն է։
Ռեկուրսիվ մոտեցման հիանալի կողմերից մեկն այն է, որ կարող եք համարել, թե ֆունկցիան ճիշտ է աշխատում «պարզ» արգումենտների դեպքում, և հետո ապահովել, որ այն ճիշտ վարվի նաև ավելի «դժվար» դեպքերի համար։ ճիշտ այնպես, ինչպես կանչում ենք sqrt, max, abs և այլ ֆունկցիաներ՝ վստահ լինելով, որ դրանք ճիշտ են աշխատում, նույն կերպ էլ ռեկուրսիայի մեջ կարող ենք ընդունել, թե մեր ֆունկցիան անհամբեր սպասվող արդյունքը կտա պարզ դեպքերի ժամանակ, և այն օգտագործենք այժմյան (ավելի բարդ) դեպքը լուծելու համար։
💡
Միակ պահանջը համոզվելն է, որ ֆունկցիան վերջապես կհասնի հիմնական դեպքին (base case)։ Հակառակ դեպքում ռեկուրսիան անսահման կշարունակվի, և մենք կհանդիպենք StackOverflow-ի!
Որպես օրինակ, եթե ցանկանում ենք հաշվել թվերի 0, 1, 2, …, n գումարը n տրված լինելու դեպքում, կարող ենք ռեկուրսիվ ֆունկցիայի մեջ իրականացնել այդ գործընթացը։
Սկսենք sum ֆունկցիայի պարզագույն տարբերակից։ Առաջին քայլը վստահ լինելն է, որ այն ճիշտ կաշխատի ամենահիմնական դեպքերի համար (n = 0 կամ 1):
def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:         # Եթե n-ը 0 է, ապա գումարը 0 է
        return 0       # Ֆունկցիայի կատարումը դադարեցնենք այստեղ
    if n == 1:         # Եթե n-ը 1 է, ապա գումարը 1 է
        return 1       # Ֆունկցիայի կատարումը դադարեցնենք այստեղ

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> None (քանի որ այս մասը դեռ չենք իրականացրել)
Այն փաստը, որ այստեղ արդեն ունենք sum(0)-ը միշտ վերադարձնում է 0, իսկ sum(1)-ը միշտ վերադարձնում է 1, կարելի է օգտագործել հենց նույն sum ֆունկցիայի ներսում, երբ այն nouvelleից կանչենք։
Հետևաբար՝ մեկ քայլ առաջ անցնենք և իրականացնենք sum-ը (2-ի և 3-ի համար), օգտագործելով արդեն պատրաստի sum(1) և sum(0) տարբերակները.
def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:             # Եթե n-ը 2 է, գումարում ենք 2-ը sum(1)-ի արդյունքին
        return n + sum(1)  # կամ n + sum(n - 1)
    if n == 3:             # Եթե n-ը 3 է, գումարում ենք 3-ը sum(2)-ի արդյունքին
        return n + sum(2)  # կամ n + sum(n - 1)

print(sum(1))          # sum(1) -> 1
print(sum(0))          # sum(0) -> 0
print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> None (քանի որ այս մասը դեռ չենք իրականացրել)
Արդյունքում, պարզ է դառնում, որ sum-ը ճիշտ է աշխատում, երբ n-ը 0, 1, 2 կամ 3 է։
Այժմ կարելի է ընդհանուրացնել ֆունկցիան ավելի մեծ արժեքների համար։ Միակ պահանջն այն է, որ ինքն իրեն կանչելիս, այն ի վերջո հասնի ավելի փոքր արժեքների (n = 0, 1, 2, 3)։ Այսինքն, եթե n = 4, ապա կարելի է ավելացնել 4-ը sum(3)-ի արդյունքին, իսկ եթե n = 5, կարելի է 5-ը գումարել sum(4)-ի արդյունքին և այսպես շարունակ.
def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n == 2:
        return n + sum(1)
    if n == 3:
        return n + sum(2)
    # Մնացած բոլոր դեպքերի համար (4, 5, 6, ...)
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> 10
# ...
Ռեկուրսիվ ֆունկցիայի հիմնական երեք տարրերն են.
  1. Base case (հիմնական դեպք): Պայման, որն ավարտում է ռեկուրսիան։ Առանց դրա, ֆունկցիան անվերջ կմնա ինքն իրեն կանչելով և կհանգեցնի անվերջ ցիկլի։ Այստեղ n == 0 և n == 1 դեպքերը հիմնական պայմաններն են:
  1. Ռեկուրսիվ քայլ: Այն մասը, որտեղ ֆունկցիան ինքն իրեն է կանչում, սովորաբար այլ արգումենտով։ Այստեղ sum(n - 1) կանչն է:
 
Քանի որ n == 1, n == 2 և n == 3 դեպքերի ռեկուրսիվ կանչերը, մեծ հաշվով, նույնն են, ինչ n == 4, n == 5 և այլն դեպքերի համար, մենք կարող ենք էլ ավելի կրճատել կոդը՝ թողնելով միայն մեկ հիմնական դեպք (n == 0).
def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:
        return 0
    return n + sum(n - 1)  

print(sum(2))          # sum(2) -> sum(1) -> sum(0) -> 3
print(sum(3))          # sum(3) -> sum(2) -> sum(1) -> sum(0) -> 6
print(sum(4))          # sum(4) -> sum(3) -> sum(2) -> sum(1) -> sum(0) -> 10
# ...
Այս ձևով, ռեկուրսիվ վստահության թռիչքն օգտագործելով, ենթադրում ենք (կամ գիտենք), որ ֆունկցիան ճիշտ է աշխատում պարզ դեպքերի համար, և դրա հիման վրա կառուցում ենք միջին և բարդ դեպքերի լուծումը։ Այն օգնում է հասկանալ, թե ինչպես են ռեկուրսիվ ֆունկցիաները աշխատում և ինչպես պետք է դրանք գրել։
💡
Ռեկուրսիվ կանչը նման է լրիվ ուրիշ ֆունկցիա կանչելուն, որի դեպքում Դուք հստակ վստահ եք, որ այն ճիշտ կաշխատի փոխանցված արգումենտների դեպքում:

Առաջադրանք

Գրել ռեկուրսիվ ֆունկցիա, որը կհաշվի n! արժեքը -ի վրա բաժանելիս ստացվող մնացորդը։

Մուտք

Մուտքը պարունակում է մեկ ամբողջ թիվ n (1 ≤ n ≤ 1000)։

Ելք

Ծրագիրը պետք է տպի n!-ի արժեքը -ով վերցրած մնացորդով (մոդի արդյունքը)։

Օրինակներ

Մուտք
Ելք
5
120
10
3628800
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue