Što je rekurzivna funkcija?
Funkcija sebe poziva iznova i iznova dok ne zadovolji rekurzivno stanje. Rekurzijska funkcija raščlanjuje problem na manje i poziva vlastitu logiku da riješi manji problem. Ova tehnika je poznata kao dijeljenje i osvajanje. Koristi se u matematici i polju informatike.
Rekurzivna funkcija uključuje bazni slučaj (ili terminalni slučaj) i rekurzivni slučaj. U osnovnom slučaju možete uzeti u obzir glavni problem koji treba riješiti i rekurzivni slučaj dijeli problem na manje dijelove dok ne dosegne razinu na kojoj ga se može lako riješiti. Rekurzivni slučaj može vratiti rezultat ili će se možda ponovno pozivati radi daljnjeg dijeljenja problema. Svaki put kada se problem raspada na manji problem, funkcija koja se zove rekurzivno sprema stanje poziva i očekuje rezultat od sebe nakon što razbije problem.
Rekurzivna funkcija u Pythonu
Koncept rekurzije ostaje isti u Pythonu. Funkcija poziva sebe da razbije problem na manje probleme. Najjednostavniji primjer koji bismo mogli pomisliti o recesiji bilo bi pronalaženje faktora iz broja.
Recimo da trebamo pronaći tvornicu broja 5 => 5! (Naš problem)
Da pronađem 5! problem se može razbiti na manje 5! => 5 x 4!
Dakle, dobiti 5! Moramo pronaći 4! i pomnožiti s 5.
Nastavimo na podjeli problema
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Kad dosegnemo i najmanji komad, tj. Dobivanje faktorije 1, možemo vratiti rezultat kao
Uzmimo primjer pseudo-koda: -
Algoritam za faktografski
Pogledajmo algoritam za faktoracije:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Funkcijski pozivi
Pretpostavimo da pronađemo faktororijul od 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
Krajnji rezultat bit će 120 gdje smo započeli s izvršavanjem funkcije. Naša rekurzijska funkcija prestat će kad se broj toliko smanji da se može dobiti rezultat.
- Prvi poziv koji dobiva faktororijum 5 rezultirat će u rekurzivnom stanju gdje će biti dodan u stog, a drugi poziv će se obaviti nakon smanjenja broja na 4.
- Ova rekurzija nastavit će pozivati i razbijati problem na manje komade dok ne dosegne osnovno stanje.
- Osnovni uvjet ovdje je kada je broj 1.
- Svaka rekurzivna funkcija ima svoje rekurzivno stanje i osnovno stanje.
Prednosti i nedostaci rekurzivne funkcije Pythona
- Izvođenje rekurzije je tako da neće raditi nikakve proračune dok ne dosegne osnovno stanje.
- Ako dođete do osnovnih uvjeta, možda će vam ponestati memorije.
- U velikom problemu u kojem može biti milijun koraka ili može se reći milijun rekurzija da biste napravili program može dovesti do pogreške u memoriji ili greške segmentacije.
- 1000000! = 1000000 * 999999! =?
- Rekurzija se razlikuje od iteracije koja se ne povećava kao iterativna metoda.
- Različiti jezici imaju različite optimizacije za rekurziju.
- U mnogim jezicima iterativna metoda bila bi bolja od rekurzije.
- Svaki jezik ima određena ograničenja zbog dubine rekurzije s kojima se možete suočiti prilikom rješavanja velikih problema.
- Ponekad je teško razumjeti složene probleme s rekurzijom, dok je iteracija prilično jednostavna.
Neki profesionalci
- U nekim je slučajevima rekurzija prikladan i brži način za korištenje.
- Vrlo korisno za presjek stabla i binarno pretraživanje.
Python Code - rekurzija vs iteracija
Razumjeli smo što je rekurzija i kako to funkcionira u Pythonu, jer znamo da svi jezici imaju različitu implementaciju rekurzije za pamćenje i računalne optimizacije. Može postojati slučaj u kojem bi iteracija bila brža od rekurzije.
Ovdje bismo usporedili i rekurziju i metodu ponavljanja da vidimo kako Python djeluje u oba slučaja.
1. rekurzijski kod za faktore
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 pomoću iteracije (petlje)
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. Ispis rezultata
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
Izlaz:
Kao što vidimo kako obojica daju isti izlaz kao što smo napisali istu logiku. Ovdje ne možemo vidjeti nikakvu razliku u izvršenju.
Dodajmo malo vremena kako bismo dobili više informacija o izvršenju rekurzije i iteracije u Pythonu.
Uvest ćemo biblioteku „vremena“ i provjeriti koliko vremena i ponavljanja treba povratiti rezultat.
4. Šifra s računanjem vremena
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))
Napravit ćemo opetovane egzekucije s različitim vrijednostima za tvornice i vidjeti rezultate. Rezultati u nastavku mogu se razlikovati od stroja do stroja. Koristili smo MacBook Pro 16 GB RAM-a i7.
Za izvršavanje koristimo Python 3.7
Slučaj 1: - Faktor 6:
Slučaj 2: Faktor od 50:
Slučaj 3: Faktor od 100:
Slučaj 4: Faktor od 500:
Slučaj 5: Faktororial 1000:
Analizirali smo obje metode u različitom problemu. Štoviše, oba su postupila slično, osim u slučaju 4.
U slučaju 5, došlo je do pogreške dok to radimo s rekurzijom.
Python je dobio ograničenje na maksimalnu dubinu koju možete ići s rekurzijom, ali isti problem sam uspio riješiti iteracijom.
Python ima ograničenja za problem prelijevanja. Python nije optimiziran za rekurziju repa, a nekontrolirana rekurzija uzrokuje prelijevanje snopa.
Funkcija "sys.getrecursionlimit ()" značila bi vam granicu za rekurziju.
Granica rekurzije može se promijeniti, ali ne preporučuje se da bi mogla biti opasna.
Zaključak - rekurzivna funkcija Pythona
- Rekurzija je prikladno rješenje za neke probleme poput prelaska drveća i drugih problema.
- Python nije funkcionalan programski jezik i vidimo da rekurzijski niz nije toliko optimiziran u usporedbi s iteracijom.
- Trebali bismo koristiti iteraciju u našem algoritmu jer je njegova optimizirana u Pythonu i daje vam bolju brzinu.
Preporučeni članci
Ovo je vodič za rekurzivnu funkciju na Pythonu. Ovdje smo raspravljali o tome što su rekurzivna funkcija, rekurzivna funkcija u Pythonu, algoritam za faktorije itd. Također možete proći i kroz druge naše predložene članke da biste saznali više -
- Čimbenik u Pythonu
- Naredbe iskre ljuske
- Najbolji C sastavljači
- Vrste algoritama
- Faktorski program u JavaScript-u
- Vodič za popis naredbi Unix Shell
- Vrste oblika u reakciji s primjerima