Ռեկուրսիա
Ծրագրավորում սովորելիս մենք առաջադրանքների հետ հաճախ աշխատում ենք գծային, պարզ ձևով: Սակայն, հնարավոր է հանդիպենք խնդիրների, որոնք պահանջում են մեր առաջադրանքները բաժանել ավելի փոքր, միանման խնդիրների: Հենց այստեղ է, որ օգնության է գալիս ռեկուրսիան:
Պարզ ասած՝ ռեկուրսիան այն երևույթն է, երբ ֆունկցիան իր կատարման ընթացքում կանչում է ինքն իրեն: Միգուցե թվա, թե այսպիսի գործողությունը կարող է անվերջ ցիկլ ստեղծել, բայց եթե ճիշտ իրականացնենք մեր ֆունկցիան, այն, ի վերջո, կհասնի մի կետի, որից հետո այլևս ինքն իրեն չի կանչի:
Պատկերացրեք մատրյոշկա տիկնիկ. ամեն անգամ, երբ տիկնիկ եք բացում, ներսում ավելի փոքր տիկնիկ կա, և դուք շարունակում եք բացել մինչև հասնեք ամենափոքր տիկնիկին, որը հնարավոր չէ բացել: Տիկնիկների բացման այս գործընթացը նման է ռեկուրսիային: Ավելի մեծ խնդիրը (առաջին տիկնիկը բացելը) լուծվում է նույն խնդրի փոքր տարբերակները մի քանի անգամ լուծելով (բացելով փոքր տիկնիկները), մինչև հասնեք մի կետի, որտեղ խնդիրը հնարավոր չէ ավելի փոքրացնել (ամենափոքր տիկնիկը):
Այս գործընթացը, որով մենք բարդ խնդիրը ռեկուրսիվ տրոհում ենք ավելի պարզ խնդիրների և լուծում դրանք, մինչև ամենապարզ խնդրի հասնելը, կարելի է հասկանալ Recursive Leap of Faith գաղափարի միջոցով։
Recursive Leap of Faith
Ռեկուրսիվ եղանակով խնդիրներ լուծելիս մենք սովորաբար ստեղծում ենք մի ֆունկցիա, որն ինչ-որ պահ ինքն իրեն կանչում է։ Այն մասը, երբ ֆունկցիան կանչում է ինքն իրեն, անվանում ենք «ռեկուրսիվ քայլ»։
Ռեկուրսիվ ֆունկցիաներ իրագործելիս կարելի է ենթադրել, որ ֆունկցիան ճիշտ է աշխատում պարզ արգումենտների վրա, որից հետո հիմնվել պարզ արգումենտներով ֆունկցիայի աշխատանքի արդյունքների վրա և իրագործել մնացած, ավելի բարդ մասը։
sqrt, max, abs և այլ ֆունկցիաներ, որոնք մենք արդեն օգտագործել ենք իմանալով, որ դրանք ճիշտ են աշխատում, կարող ենք ենթադրել, որ մեր ֆունկցիան ճիշտ է աշխատում փոքր/պարզ արգումենտների համար, և օգտագործել դրանց արդյունքները տվյալ պահի արգումենտների համար ճիշտ արդյունքը ստանալու համար։💡
Միակ և ամենակարևոր պայմանը ռեկուրսիվ ֆունկցիա իրականացնելիս՝ պետք է վստահ լինել, որ ֆունկցիան կհասնի բազային (ամենապարզ) դեպքին, որը չի կանչի այդ ֆունկցիան։
Հակառակ դեպքում ծրագիրը անվերջ ցիկլի մեջ կնկնի և կստանա StackOverflow սխալ։
Ռեկուրսիվ ֆունկցիայի օրինակ դիտարկելու համար, եկեք փորձենք հաշվել
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
# ...Ռեկուրսիվ ֆունկցիայի հիմնական մասերն են.
- Բազային դեպքը. Պայման, որը դադարեցնում է ռեկուրսիան: Առանց դրա, ֆունկցիան անդադար կկանչեր ինքն իրեն` առաջացնելով անվերջ ցիկլ: Այս դեպքում դա
n == 0-ն է:
- Ռեկուրսիվ քայլը․ Այն մասն է, որտեղ ֆունկցիան կանչում է ինքն իրեն, սովորաբար այլ արգումենտով: Այստեղ՝
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 մենք ենթադրում ենք (կամ վստահ լինում), որ ֆունկցիան ճիշտ է աշխատում փոքր/պարզ դեպքերի համար, որը վրա հիմնվելով կառուցում ենք ֆունկցիայի ճիշտ աշխատանքը մնացած բոլոր դեպքերի համար։
💡
Ֆունկցիան ռեկուրսիվ կանչելը նման է մեկ այլ ֆունկցիայի կանչին, որի դեպքում մենք վստահ ենք, որ արդյունքը ճիշտ է փոխանցված արգումենտների դեպքում։