Kaj je rekurzivna funkcija?
Funkcija kliče vedno znova, dokler ne izpolni rekurzivnega stanja. Rekurzijska funkcija razbije težavo na manjše težave in pokliče svojo logiko, da reši manjši problem. Ta tehnika je znana kot »deli in osvoji«. Uporablja se v matematiki in na področju računalništva.
Rekurzivna funkcija vključuje osnovni slučaj (ali terminalski slučaj) in rekurzivni primer. V osnovnem primeru lahko razmislite o največji težavi, ki jo je treba rešiti, in rekurzivni primer razdeli težavo na manjše dele, dokler ne doseže ravni, kjer jo je mogoče hitro rešiti. Rekurzivni primer lahko vrne rezultat ali pa se lahko sam spet pokliče, da težavo še razdeli. Vsakič, ko se težava razbije na manjši problem, funkcija, ki jo kličete, rekurzivno shrani stanje klica in pričakuje rezultat od sebe po razpadu težave.
Rekurzivna funkcija v Pythonu
Koncept rekurzije ostaja enak pri Pythonu. Funkcija sama kliče, da razčleni težavo na manjše težave. Najpreprostejši primer, ki bi si ga lahko zamislili o rekurziji, bi bilo iskanje faktorjev števil.
Recimo, da moramo najti faktor s številko 5 => 5! (Naša težava)
Najti 5! težavo lahko razbijemo na manjše 5! => 5 x 4!
Torej, da bi dobili 5! Najti moramo 4! in pomnožite s 5.
Nadaljujmo z deljenjem težave
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Ko dosežemo najmanjši del, tj. Dobimo faktor 1, lahko rezultat vrnemo kot
Vzemimo primer psevdo kod: -
Algoritem za faktororial
Poglejmo algoritem za faktororial:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Funkcijski klici
Recimo, da najdemo faktorjev 5.
get_factorial(5) 5 * get_factorial(4) = returns 120 #1st call
get_factorial(4) 4 * get_factorial(3) = returns 24 #2nd call
get_factorial(3) 3 * get_factorial(2) = returns 6 #3rd call
get_factorial(2) 2 * get_factorial(1) = returns 2 #4th call
get_factorial(1) returns 1 #5th call
Končni rezultat bo 120, kjer smo začeli z izvajanjem funkcije. Naša rekurzijska funkcija se ustavi, ko je število tako zmanjšano, da lahko dobimo rezultat.
- Prvi klic, ki dobi faktor 5, bo povzročil rekurzivno stanje, ko bo dodan v sveženj, drugi klic pa po zmanjšanju števila na 4.
- Ta rekurzija bo še naprej klicala in razbijala težavo na manjše koščke, dokler ne doseže osnovnega stanja.
- Osnovni pogoj tukaj je, ko je število 1.
- Vsaka rekurzivna funkcija ima svoje rekurzivno stanje in osnovno stanje.
Prednosti in slabosti rekurzivne funkcije Pythona
- Rekurzija se izvede tako, da ne bo opravila nobenih izračunov, dokler ne doseže osnovnega stanja.
- Če dosežete osnovne pogoje, vam lahko zmanjka pomnilnika.
- Pri velikih težavah, kjer je lahko milijon korakov ali pa recimo milijon rekurzij, da program opravi, lahko pride do napake v pomnilniku ali napake segmentacije.
- 1000000! = 1000000 * 999999! =?
- Rekurzija je drugačna kot iteracija, ki se ne poveča kot iterativna metoda.
- Različni jeziki imajo različne optimizacije za rekurzijo.
- V mnogih jezikih bi iterativna metoda delovala bolje kot rekurzija.
- Vsak jezik ima nekaj omejitev glede globine rekurzije, s katerimi se lahko srečujete pri reševanju velikih težav.
- Včasih je težko razumeti zapletene težave z rekurzijo, medtem ko je z iteracijo precej preprosto.
Nekaj prednosti
- V nekaterih primerih je rekurzija priročen in hitrejši način uporabe.
- Zelo koristno pri prečkanju drevesa in binarnem iskanju.
Python Code - rekurzija proti ponovitvi
Razumeli smo, kaj je rekurzija in kako deluje v Pythonu, saj vemo, da imajo vsi jeziki različne izvedbe rekurzije za pomnilnik in računalniške optimizacije. Lahko pride do primera, ko bi iteracija potekala hitreje kot rekurzija.
Tu bi primerjali tako rekurzijsko kot iteracijsko metodo, da bi videli, kako deluje Python v obeh primerih.
1. Rekurzijska koda za Factorial
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2: #base condition
return 1
else:
return n * get_recursive_factorial(n -1) #recursion condition
2. Faktorski problem z uporabo iteracije (zanke)
def get_iterative_factorial(n):
if n < 0:
return -1
else:
fact = 1
for i in range( 1, n+1 ):
fact *= i
return fact
3. Rezultati tiskanja
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Izhod:
Kot vidimo, da oba dajeta enak izid, kot smo napisali isto logiko. Tukaj ne vidimo nobene razlike v izvedbi.
Dodajmo nekaj časovne kode, da dobimo več informacij o izvedbi rekurzije in iteracije v Pythonu.
Uvozili bomo knjižnico "časa" in preverili, koliko časa in ponovitev trajata, da rezultat vrnemo.
4. Koda z izračunom časa
import time
def get_recursive_factorial(n):
if n < 0:
return -1
elif n < 2:
return 1
else:
return n * get_recursive_factorial(n-1)
def get_iterative_factorial(n):
if n < 0 :
return -1
else:
fact = 1
for i in range(1, n+1):
fact *= i
return fact
start_time = time.time()
get_recursive_factorial(100)
print("Recursion--- %s seconds ---" % (time.time() - start_time))
start_time = time.time()
get_iterative_factorial(100)
print("Iteration--- %s seconds ---" % (time.time() - start_time))
Naredili bomo večkratne usmrtitve z drugačno vrednostjo za faktororial in videli rezultate. Spodnji rezultati se lahko razlikujejo od stroja do stroja. Uporabili smo MacBook Pro 16 GB RAM i7.
Za izvedbo uporabljamo Python 3.7
Primer 1: - Dejavnik 6:
Primer 2: Faktororial of 50:
Primer 3: Dejavnik 100:
Primer 4: Faktororial 500:
Primer 5: Faktororial 1000:
Obe metodi smo analizirali v drugačni težavi. Poleg tega sta oba opravila podobno, razen primera 4.
V primeru 5 smo pri napaki prišlo do napake.
Python je dobil omejitev največje globine, ki jo lahko greste z rekurzijo, vendar sem isti problem rešil z iteracijo.
Python ima omejitve glede težave s prelivom. Python ni optimiziran za rekurzijo repa, nenadzorovana rekurzija pa povzroči preliv svežnja.
Funkcija „sys.getrecursionlimit ()“ bi vam povedala mejo za rekurzijo.
Mejo rekurzije se lahko spremeni, vendar ni priporočljivo, saj je lahko nevarna.
Zaključek - rekurzivna funkcija Pythona
- Rekurzija je priročna rešitev za nekatere težave, kot so prečkanje dreves in druge težave.
- Python ni funkcionalen programski jezik in vidimo, da rekurzijski sklad ni tako optimiziran v primerjavi z iteracijo.
- V našem algoritmu bi morali uporabiti iteracijo, saj je ta bolj optimiziran v Pythonu in vam omogoča boljšo hitrost.
Priporočeni članki
To je vodnik za rekurzivno funkcijo v Pythonu. Tukaj razpravljamo o tem, kaj so rekurzivna funkcija, rekurzivna funkcija v Pythonu, algoritem za faktorije itd. Če želite izvedeti več, lahko preberete tudi druge predloge.
- Factorial v Pythonu
- Iskreni ukazi lupine
- Najboljši C prevajalci
- Vrste algoritmov
- Faktorski program v JavaScript
- Vodnik po seznamu ukazov školjke Unix
- Vrste obrazcev v reagiranju s primeri