Ռեկուրսիա

Ծրագրավորում սովորելիս մենք առաջադրանքների հետ հաճախ աշխատում ենք գծային, պարզ ձևով: Սակայն, հնարավոր է, հանդիպենք խնդրի, որը պահանջում է մեր առաջադրանքը բաժանել ավելի փոքր, միանման խնդիրների: Հենց այստեղ է, որ օգնության է գալիս ռեկուրսիան:
Պարզ ասած՝ ռեկուրսիան այն երևույթն է, երբ ֆունկցիան իր կատարման ընթացքում կանչում է ինքն իրեն: Միգուցե թվա, թե այսպիսի գործողությունը կարող է անվերջ օղակ ստեղծել, բայց եթե ճիշտ ձևակերպենք մեր ֆունկցիան, այն, ի վերջո, կհասնի մի կետի, որից հետո այլևս ինքն իրեն չի կանչի:
Նախքան կոդ գրելը, եկեք սկսենք մեզ ծանոթ օրինակից:
Պատկերացրեք մատրյոշկա տիկնիկ. ամեն անգամ, երբ տիկնիկ եք բացում, ներսում ավելի փոքր տիկնիկ կա, և դուք շարունակում եք բացել մինչև հասնեք ամենափոքր տիկնիկին, որը հնարավոր չէ բացել: Տիկնիկների բացման այս գործընթացը նման է ռեկուրսիային: Ավելի մեծ խնդիրը (առաջին տիկնիկը բացելը) լուծվում է նույն խնդրի փոքր տարբերակները մի քանի անգամ լուծելով (բացելով փոքր տիկնիկները), մինչև հասնեք մի կետի, որտեղ խնդիրը հնարավոր չէ ավելի փոքրացնել (ամենափոքր տիկնիկը):
notion image
Այժմ եկեք կիրառենք այս կոնցեպտը Python ֆունկցիայի վրա.
def countdown(n):
    if n <= 0:
        # Base case: we've reached zero or below, so we stop
        print('Blastoff!')
    else:
        # Recursive case: print the current number and countdown from n-1
        print(n)
        countdown(n - 1)
Այս ֆունկցիայի մեջ countdown(5)-ը տպում է 5, այնուհետև կանչում է countdown(4), որը տպում է 4-ը, այնուհետև կանչում է countdown(3) և այսպես շարունակ, մինչև հասնենք countdown(0),-ին որը դադարեցնում է ռեկուրսիան և տպում Blastoff!:
Փորձարկենք ֆունկցիան.
countdown(5)
Ելքը կլինի.
5
4
3
2
1
Blastoff!
Դուք կարող եք տեսնել ռեկուրսիան գործողության մեջ, որտեղ 5-ից հետ հաշվելու խնդիրը բաժանվում է 4-ից, 3-ից, 2-ից, 1-ից և վերջապես 0-ից հետհաշվելու խնդիրների:
Ռեկուրսիվ ֆունկցիայի հիմնական մասերն են.
  1. Բազային պայմանը. Պայման, որը դադարեցնում է ռեկուրսիան: Առանց դրա, ֆունկցիան անդադար կկանչեր ինքն իրեն` առաջացնելով անվերջ ցիկլ: Այս դեպքում դա n <= 0-ն է:
  1. Ռեկուրսիվ պայմանը․ Այն պայմանն է, որտեղ ֆունկցիան կանչում է ինքն իրեն, սովորաբար այլ արգումենտով: Այստեղ՝ countdown(n - 1):
Ռեկուրսիան իսկապես հետաքրքրաշարժ հասկացություն է: Այն նման է կախարդական գործիքի, որը դուք պահում եք ծրագրավորման գործիքների ձեր տուփում, և որը թույլ է տալիս բարդ խնդիրները բաժանել փոքր, ավելի պարզ մասերի: Այլ կերպ ասած՝ սա գլուխկոտրուկ լուծելու նման մի առաջադրանք է. ամբողջական նկարը բարդ է, սակայն երբ մեկ առ մեկ հավաքում եք փազլի կտորները, ամբողջ պատկերն աստիճանաբար սկսում է ի հայտ գալ։
Video preview
A video by Reducible - 5 Simple Steps for Solving Any Recursive Problem
Իսկ ինչպե՞ս կարելի է հաշվարկներ կատարել ռեկուրսիվ ֆունկցիայի ներսում։ Որպես օրինակ՝ մենք կարող ենք փորձել հաշվարկել 1…n բոլոր թվերի գումարը՝ ունենալով n թիվը:
def sum(n):
    print(f'sum() called with argument {n}')
    if n == 1:         # In case the given number is 1 => the sum is 1 as well
        return 1       # Return here and don't execute the following commands
    prev = sum(n - 1)  # Compute the sum for 1...(n-1)
    
    print(f'Adding current {n} to prev {prev}')
    return n + prev    # Return n + the sum for 1...(n-1)

print(sum(10))
Սա կտպի բոլոր կանչերը և վերջում՝ 55 թիվը.
sum() called with argument 10
sum() called with argument 9
sum() called with argument 8
sum() called with argument 7
sum() called with argument 6
sum() called with argument 5
sum() called with argument 4
sum() called with argument 3
sum() called with argument 2
sum() called with argument 1
Adding current 2 to prev 1
Adding current 3 to prev 3
Adding current 4 to prev 6
Adding current 5 to prev 10
Adding current 6 to prev 15
Adding current 7 to prev 21
Adding current 8 to prev 28
Adding current 9 to prev 36
Adding current 10 to prev 45
55
Recursive leap of faith (խնդիրները լուծում ենք՝ հիմնվելով փոքր, հաջողված լուծումների վրա): Ռեկուրսիվ լուծումների դեպքում լավն այն է, որ մենք կարող ենք ենթադրել, որ ֆունկցիան ճիշտ է աշխատում, եթե ճիշտ են աշխատում պարզ արգումենտները, որից հետո կարող ենք լուծել խնդիրը՝ հիմնվելով այդ պարզ արգումենտների ճիշտ աշխատանքի վրա։ Օրինակ, sqrt ֆունկցիան կանչելու նմանությամբ, դուք կարող եք ենթադրել, որ ֆունկցիան աշխատում է ավելի փոքր/պարզ արգումենտների համար և կանչել ֆունկցիան այդ արգումենտներով, որից հետո դրանց վրա կառուցել ներկայիս արդյունքը: Միակ պահանջը համոզվելն է, որ ֆունկցիան կհասնի բազային պայմանին (ինչպես n == 1-ը մեր օրինակում), հակառակ դեպքում մենք կունենանք անվերջ գործող ռեկուրսիվ ֆունկցիա և կարող ենք ստանալ StackOverflow:
1-ից մինչև n թվերի գումարը հաշվարկելու դեպքում ռեկուրսիվ լուծումն իրենից կենթադրի, որ ֆունկցիան ճիշտ է հաշվարկել նախորդ գումարը (n-1-ի գումարը - prev = sum (n - 1)) և այդ ենթադրության հիման վրա կկառուցի ընթացիկ պատասխանը։ Այսպիսով, եթե ընթացիկ n-ը 6 է, մենք կարող ենք ենթադրել, որ sum(5)-ը ճիշտ կաշխատի և, հետևաբար, վերջում կվերադարձնի 6 գումարած sum(5)-ի արդյունքը:
 
To check your solution you need to sign in
Sign in to continue