Ռեկուրսիա

Ծրագրավորում սովորելիս մենք առաջադրանքների հետ հաճախ աշխատում ենք գծային, պարզ ձևով: Սակայն, հնարավոր է հանդիպենք խնդիրների, որոնք պահանջում են մեր առաջադրանքները բաժանել ավելի փոքր, միանման խնդիրների: Հենց այստեղ է, որ օգնության է գալիս ռեկուրսիան:

Պարզ ասած՝ ռեկուրսիան այն երևույթն է, երբ ֆունկցիան իր կատարման ընթացքում կանչում է ինքն իրեն: Միգուցե թվա, թե այսպիսի գործողությունը կարող է անվերջ ցիկլ ստեղծել, բայց եթե ճիշտ իրականացնենք մեր ֆունկցիան, այն, ի վերջո, կհասնի մի կետի, որից հետո այլևս ինքն իրեն չի կանչի:

Պատկերացրեք մատրյոշկա տիկնիկ. ամեն անգամ, երբ տիկնիկ եք բացում, ներսում ավելի փոքր տիկնիկ կա, և դուք շարունակում եք բացել մինչև հասնեք ամենափոքր տիկնիկին, որը հնարավոր չէ բացել: Տիկնիկների բացման այս գործընթացը նման է ռեկուրսիային: Ավելի մեծ խնդիրը (առաջին տիկնիկը բացելը) լուծվում է նույն խնդրի փոքր տարբերակները մի քանի անգամ լուծելով (բացելով փոքր տիկնիկները), մինչև հասնեք մի կետի, որտեղ խնդիրը հնարավոր չէ ավելի փոքրացնել (ամենափոքր տիկնիկը):

Այս գործընթացը, որով մենք բարդ խնդիրը ռեկուրսիվ տրոհում ենք ավելի պարզ խնդիրների և լուծում դրանք, մինչև ամենապարզ խնդրի հասնելը, կարելի է հասկանալ Recursive Leap of Faith գաղափարի միջոցով։

Recursive Leap of Faith

Ռեկուրսիվ եղանակով խնդիրներ լուծելիս մենք սովորաբար ստեղծում ենք մի ֆունկցիա, որն ինչ-որ պահ ինքն իրեն կանչում է։ Այն մասը, երբ ֆունկցիան կանչում է ինքն իրեն, անվանում ենք «ռեկուրսիվ քայլ»։

Ռեկուրսիվ ֆունկցիաներ իրագործելիս կարելի է ենթադրել, որ ֆունկցիան ճիշտ է աշխատում պարզ արգումենտների վրա, որից հետո հիմնվել պարզ արգումենտներով ֆունկցիայի աշխատանքի արդյունքների վրա և իրագործել մնացած, ավելի բարդ մասը։ sqrt, max, abs և այլ ֆունկցիաներ, որոնք մենք արդեն օգտագործել ենք իմանալով, որ դրանք ճիշտ են աշխատում, կարող ենք ենթադրել, որ մեր ֆունկցիան ճիշտ է աշխատում փոքր/պարզ արգումենտների համար, և օգտագործել դրանց արդյունքները տվյալ պահի արգումենտների համար ճիշտ արդյունքը ստանալու համար։

Ռեկուրսիվ ֆունկցիայի օրինակ դիտարկելու համար, եկեք փորձենք հաշվել 0, 1, 2, …, n թվերի գումարը՝ ունենալով n թիվը։

Փորձենք քայլ առ քայլ իրականացնել sum ֆունկցիան։ Որպես առաջին քայլ սահմանենք պարզագուն դեպքերը, որոնք պետք է վերադարձնեն sum ֆունկցիայի արդյունքը, երբ n-ը 0 է կամ 1։

def sum(n):
    print(f'sum({n})', end=' -> ')
    if n == 0:         # Երբ n-ը 0 է => sum ը 0 է
        return 0       # Կանգնեցնել ֆունկցիայի աշխատանքն այստեղ
    if n == 1:         # Երբ n-ը 1 է => sum ը 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 ֆունկցիան 0 կամ 1 արգումենտներով նույնիսկ հենց sum ֆունկցիայի մեջ՝ վստահ լինելով, որ արդյունքները ճիշտ կլինեն։

Մենք կարող ենք ևս մեկ քայլ առաջ գնալ և իրականացնել sum ֆունկցիան n = 2 և n = 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) դեպքերի համար:

Սա ունենալով մենք կարող ենք արդեն իրականացնել sum ֆունկցիան n-ի ավել մեծ դեպքերի համար։ Միակ պայմանը այն է, որ այդ մեծ դեպքերի աշխատանքը պետք է ավարտվի ի վերջո հասնելով ավելի պարզ 0, 1, 2 և 3 դեպքերին։ Այդպիսով մենք կկարողանանք իրականացնել sum ֆունկցիան ավելի մեծ՝ 4, 5 կամ 6 թվերի համար օգտագործելով փոքր թվերի համար արդյունքները։

sum(4)-ը հաշվելու համար մենք կարող ենք օգտագործել sum(3)-ի արդյունքը։ sum(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. Բազային դեպքը. Պայման, որը դադարեցնում է ռեկուրսիան: Առանց դրա, ֆունկցիան անդադար կկանչեր ինքն իրեն` առաջացնելով անվերջ ցիկլ: Այս դեպքում դա n == 0-ն է:

2. Ռեկուրսիվ քայլը․ Այն մասն է, որտեղ ֆունկցիան կանչում է ինքն իրեն, սովորաբար այլ արգումենտով: Այստեղ՝ sum(n - 1)-ը:

Քանի որ n == 1, n == 2 և n == 3 դեպքերը լրիվ համընկնում են n == 4, n == 5 և այլ դեպքրին իրենց իրականացմամբ՝ մենք կարող ենք պարզեցնել sum ֆունկցիան թողնելով միայն մեկ բազային դեպք (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
# ...

Այսպես կիրառելով recursive leap of faith մենք ենթադրում ենք (կամ վստահ լինում), որ ֆունկցիան ճիշտ է աշխատում փոքր/պարզ դեպքերի համար, որը վրա հիմնվելով կառուցում ենք ֆունկցիայի ճիշտ աշխատանքը մնացած բոլոր դեպքերի համար։