Вы калі-небудзь траплялі ў, здавалася б, бясконцы цыкл, калі праблема працягвае разгаліноўвацца на больш дробныя фрагменты?
Калі так, магчыма, вы трапілі ў захапляльны свет рэкурсіі. Нягледзячы на тое, што гэта можа здацца складаным для разумення, не хвалюйцеся! У гэтым пасце мы адправімся ў цікавае падарожжа, каб даведацца пра тыпы рэкурсій.
Так што прышпіцеся, калі мы вывучаем шматлікія рэкурсіўныя падыходы. Падрыхтуйцеся ўвайсці ў захапляльнае царства рэкурсіі і назірайце за яе выдатнымі здольнасцямі ў вырашэнні складаных задач.
Што такое рэкурсіі?
Прасцей кажучы, рэкурсія - гэта магутная тэхніка праграмавання, якая ўключае ў сябе выклік самой функцыі падчас выканання. Гэта падобна на тое, каб глядзець у люстэрка і бачыць выяву ўнутры выявы, што прыводзіць да самарэферэнтнага цыклу.
Мы можам вырашаць вялікія праблемы з дапамогай рэкурсіі, падзяляючы іх на меншыя, больш кіраваныя падзадачы.
Гэта падобна на складанне лобзіка, дзе адна частка злучаецца з іншымі часткамі, каб стварыць поўную карціну. Рэкурсія дазваляе нам вырашаць праблемы элегантным і эфектыўным спосабам, паўтараючы адзін і той жа набор інструкцый з рознымі ўводамі.
1-Прамая рэкурсія
Прамая рэкурсія - гэта самы асноўны тып рэкурсіі, пры якім функцыя выклікае непасрэдна саму сябе. Гэта цягне за сабой падзел праблемнай праблемы на больш дробныя падзадачы, пакуль не будзе дасягнуты базавы варыянт, што прыводзіць да спынення.
Рэкурсіўная функцыя выклікае сябе з рознымі ўводамі, што дазваляе паўтарыць выкананне аднаго і таго ж набору інструкцый. Кожны выклік абапіраецца на папярэдні, паступова набліжаючыся да базавага выпадку, што прыводзіць да завяршэння рэкурсіі.
Давайце праверым гэты прыклад.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Вынахад:
5
4
3
2
1
2-Ускосная рэкурсія
Ускосная рэкурсія дадае інтрыгуючы паварот рэкурсіўнаму шляху. У адрозненне ад прамой рэкурсіі, якая ўключае ў сябе відавочны выклік функцыі, ускосная рэкурсія ўключае ў сябе ланцужок выклікаў функцый.
Адна функцыя выклікае іншую, якая затым можа выклікаць зыходную функцыю або любую іншую функцыю, якая ў выніку вяртаецца да зыходнага. Гэтая ўзаемазвязаная сетка выклікаў функцый стварае захапляльны танец, у якім некалькі функцый супрацоўнічаюць, каб вырашыць праблему.
прыклад:
def function_A(n):
if n > 0:
print("A:", n)
function_B(n - 1)
def function_B(n):
if n > 0:
print("B:", n)
function_A(n - 1)
function_A(3)
Вынахад:
A: 3
B: 2
A: 1
3-лінейная рэкурсія
Падумайце аб падарожжы па прамым маршруце, крок за крокам, пакуль не дасягнеце мэты. Гэтая паслядоўная тэхніка ўвасоблена ў лінейнай рэкурсіі, у якой функцыя выконвае адзін рэкурсіўны выклік у кожнай ітэрацыі функцыі.
З кожным рэкурсіўным выклікам рэкурсіўны працэс набліжаецца да базавага выпадку, памяншаючы памер выпуску. Яно адбываецца ясным і лінейным чынам, вырашаючы падзадачы адну за адной, пакуль не будзе дасягнуты канчатковы адказ.
прыклад:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Вынахад:
120
4-дрэвавая рэкурсія
Калі функцыя разгаліноўваецца на некалькі рэкурсіўных выклікаў, мы трапляем у свет дрэвападобнай рэкурсіі. Функцыя ў дрэве рэкурсіі генеруе мноства рэкурсіўных выклікаў, кожны з якіх вырашае асобную падзадачу, як гэта робяць галіны дрэва.
Гэтая разгалінаваная структура дазваляе адначасовае расследаванне некалькіх маршрутаў, эфектыўна разбіваючы складаныя пытанні на больш дробныя, узаемазвязаныя кампаненты.
прыклад:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Вынахад:
8
5-ўкладзеная рэкурсія
Укладзеная рэкурсія дадае захапляльную ступень складанасці ў рэкурсіўны сусвет. У гэтай форме рэкурсіі функцыя ўключае рэкурсіўны выклік у якасці аргумента ў іншы рэкурсіўны выклік.
Унутраны рэкурсіўны выклік дзейнічае на значэнне, якое залежыць ад вонкавага рэкурсіўнага выкліку. Складанасць расце з кожным укладзеным выклікам, кульмінацыяй якога з'яўляецца інтрыгуючая мадэль укладзеных рэкурсіўных выклікаў.
прыклад:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Вынік:
91
6-хваставая рэкурсія
Хваставая рэкурсія - гэта метад аптымізацыі рэкурсіўных алгарытмаў, які можа палепшыць іх прадукцыйнасць. Рэкурсіўны выклік выглядае як канчатковае дзеянне функцыі з хваставой рэкурсіяй.
Паколькі пасля рэкурсіўнага выкліку няма невыкананых аперацый, кампілятар або інтэрпрэтатар можа спрасціць рэкурсію, замяніўшы яе простым пераходам.
Гэты падыход да аптымізацыі, вядомы як аптымізацыя хваставога выкліку, зніжае патрабаванне для кожнага рэкурсіўнага выкліку захоўваць кадр стэка, што прыводзіць да павышэння хуткасці і меншага выкарыстання памяці.
прыклад:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Выхад:
120
7-Без хваставой рэкурсіі
У адрозненне ад хваставой рэкурсіі, нехваставая рэкурсія ўключае дадатковыя дзеянні, якія выконваюцца пасля рэкурсіўнага выкліку ў функцыі. Перад выкананнем якіх-небудзь іншых дзеянняў кожны рэкурсіўны выклік павінен завяршыцца і вярнуцца.
Як следства, пакуль не будзе дасягнуты базавы варыянт і не скончыцца рэкурсія, захоўваецца стэк незавершаных аперацый. Нехваставая рэкурсія часта выкарыстоўвае больш памяці і менш эфектыўная, чым хваставая рэкурсія, але яна па-ранейшаму з'яўляецца карысным інструментам для вырашэння розных праблем.
прыклад:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Вынахад:
15
хутацца
Рэкурсія - гэта інтрыгуючае паняцце ў праграмаванні. Гэта дазваляе нам вырашаць складаныя праблемы ў рэкурсіўнай, самарэферэнтнай манеры.
Ён прапануе асобны метад разважання і вырашэння праблем, разбіваючы іх на больш дробныя, больш кіраваныя часткі. Аднак пры працы з рэкурсіяй вельмі важна звярнуць увагу на некаторыя моманты.
Вы павінны вызначыць прыдатныя базавыя выпадкі, якія дазваляюць завяршыць рэкурсію. Калі яны адсутнічаюць, функцыя можа працягваць выклікаць сябе вечна.
Па-другое, зыходзячы з разгляданага сцэнарыя, выбар адпаведнага віду рэкурсіі можа прывесці да больш эфектыўных і элегантных рашэнняў. Паспрабуйце знайсці тое, што лепш за ўсё падыходзіць для праблемы ў руцэ. Працуючы з вялікай глыбінёй рэкурсіі, майце на ўвазе патэнцыйныя небяспекі, такія як перапаўненне стэка.
Пакінуць каментар