Kas olete kunagi sattunud näiliselt lõppematusse tsüklisse, kus probleem hargneb üha väiksemateks kildudeks?
Kui jah, siis olete võib-olla sattunud rekursioonide kütkestavasse maailma. Kuigi selle mõistmine võib tunduda keeruline, ärge muretsege! Selles postituses läheme huvitavale teekonnale, et õppida tundma rekursioonitüüpe.
Nii et pange kinni, kui uurime paljusid rekursiivseid lähenemisviise. Valmistuge sisenema rekursiooni põnevasse valdkonda ja jälgige selle märkimisväärset võimet keeruliste probleemide lahendamisel.
Mis täpselt on rekursioonid?
Põhisõnu öeldes on rekursioon võimas programmeerimistehnika, mis sisaldab funktsiooni, mis kutsub ennast täitmise ajal. See on nagu peeglisse vahtimine ja pildi sees kujutise nägemine, mille tulemuseks on enesele viitav tsükkel.
Rekursiooni abil saame lahendada suuri probleeme, jagades need väiksemateks, paremini juhitavateks alamprobleemideks.
See sarnaneb pusle kokkupanemisega, kus üks tükk ühendatakse teiste osadega, et luua täielik pilt. Rekursioon võimaldab meil lahendada probleeme elegantselt ja tõhusalt, korrates samu juhiseid erinevate sisenditega.
1-Otsene rekursioon
Otsene rekursioon on kõige elementaarsem rekursiooni tüüp, mille puhul funktsioon kutsub ennast otse. See hõlmab probleemse probleemi jagamist väiksemateks alamprobleemideks, kuni saavutatakse baasjuhtum, mis viib lõpetamiseni.
Rekursiivne funktsioon kutsub end erinevate sisenditega, võimaldades korrata sama käskude komplekti täitmist. Iga kutsumine tugineb eelmisele, lähenedes järk-järgult baasjuhtumile, mis põhjustab rekursiooni lõppemise.
Kontrollime seda näidet.
def countdown(n):
if n <= 0:
return
print(n)
countdown(n - 1)
countdown(5)
Väljund:
5
4
3
2
1
2-kaudne rekursioon
Kaudne rekursioon lisab rekursiivsele teele intrigeeriva pöörde. Vastupidiselt otsesele rekursioonile, mis hõlmab funktsiooni selgesõnalist isekutsumist, hõlmab kaudne rekursioon funktsioonikutsete ahelat.
Üks funktsioon kutsub välja teise, mis saab seejärel kutsuda algse funktsiooni või mis tahes muud funktsiooni, mis lõpuks naaseb originaalile. See ühendatud funktsioonikutsete võrk loob kaasahaarava tantsu, milles mitu funktsiooni teevad probleemi lahendamiseks koostööd.
Näide:
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)
Väljund:
A: 3
B: 2
A: 1
3-lineaarne rekursioon
Kaaluge teekonda mööda sirget marsruuti, üks samm korraga, kuni jõuate eesmärgini. Seda järjestikust tehnikat kehastab lineaarne rekursioon, mille puhul funktsioon sooritab igas funktsiooni iteratsioonis ühe rekursiivse väljakutse.
Iga rekursiivse kõnega liigub rekursiivne protsess põhijuhule lähemale, vähendades probleemi suurust. See kulgeb selgelt ja lineaarselt, lahendades alamprobleeme ükshaaval kuni lõpliku vastuseni.
Näide:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
result = factorial(5)
print(result)
Väljund:
120
4-puu rekursioon
Kui funktsioon hargneb mitmeks rekursiivseks väljakutseks, siseneme puurekursiooni maailma. Puu rekursiooni funktsioon genereerib palju rekursiivseid väljakutseid, millest igaüks lahendab eraldi alamprobleemi, nagu seda teevad puu oksad.
See hargnev struktuur võimaldab samaaegselt uurida mitut marsruuti, jaotades keerulised probleemid tõhusalt väiksemateks omavahel seotud komponentideks.
Näide:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
result = fibonacci(6)
print(result)
Väljund:
8
5-pesastatud rekursioon
Pesastatud rekursioon lisab rekursiivsele universumile põneva keerukuse. Selles rekursiooni vormis sisaldab funktsioon rekursiivset väljakutset argumendina teises rekursiivses kutses.
Sisemine rekursiivne kõne toimib väärtusel, mis sõltub välisest rekursiivsest kõnest. Keerukus kasvab iga pesastatud kutsumisega, mis tipneb intrigeeriva pesastatud rekursiivsete kõnede mustriga.
Näide:
def nested_recursion(n):
if n > 100:
return n - 10
return nested_recursion(nested_recursion(n + 11))
result = nested_recursion(95)
print(result)
Tulemus:
91
6-saba rekursioon
Tail rekursioon on rekursiivsete algoritmide optimeerimistehnika, mis võib parandada nende jõudlust. Rekursiivne kutse ilmub funktsiooni lõpptoiminguna koos sabarekursiooniga, tegemisega.
Kuna pärast rekursiivset kõnet pole ühtegi silmapaistvat operatsiooni, saab kompilaator või tõlk rekursiooni lihtsustada, asendades selle lihtsa hüppega.
See optimeerimisviis, mida tuntakse sabakõne optimeerimisena, vähendab iga rekursiivse kõne nõuet virnaraami säilitamiseks, mille tulemuseks on suurem kiirus ja väiksem mälukasutus.
Näide:
def tail_factorial(n, result=1):
if n == 0:
return result
return tail_factorial(n - 1, result * n)
result = tail_factorial(5)
print(result)
Väljas:
120
7-mitte-saba rekursioon
Erinevalt sabarekursioonist hõlmab mittesabarekursioon lisategevusi, mis tehakse pärast funktsiooni rekursiivset väljakutset. Enne täiendavate toimingute tegemist peab iga rekursiivne kõne lõpule jõudma ja tagasi pöörduma.
Selle tulemusel säilitatakse kuni baasjuhtumini jõudmiseni ja rekursiooni lõpuni täitmata toimingute virn. Mitte-sabarekursioon kasutab sageli rohkem mälu ja on vähem tõhus kui sabarekursioon, kuid see on siiski kasulik tööriist mitmesuguste probleemide lahendamisel.
Näide:
def non_tail_sum(n):
if n == 0:
return 0
return n + non_tail_sum(n - 1)
result = non_tail_sum(5)
print(result)
Väljund:
15
Pakkima
Rekursioon on programmeerimises intrigeeriv kontseptsioon. See võimaldab meil lahendada keerulisi probleeme rekursiivsel ja enesele viitaval viisil.
See pakub selget meetodit probleemidele mõtlemiseks ja nende lahendamiseks, jagades need väiksemateks, paremini juhitavateks tükkideks. Rekursiooniga töötades on aga oluline pöörata tähelepanu mõnele punktile.
Peaksite tuvastama sobivad baasjuhud, mis võimaldavad rekursioonil lõpetada. Kui neid pole, võib funktsioon end igavesti kutsuda.
Teiseks, vastavalt käesolevale stsenaariumile võib sobiva rekursioonitüübi valimine viia tõhusamate ja elegantsemate lahendusteni. Proovige leida, mis käes oleva probleemi jaoks kõige paremini sobib. Suurte rekursioonisügavustega töötades olge teadlik võimalikest ohtudest, nagu virna ülevool.
Jäta vastus