Š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 -

  1. Čimbenik u Pythonu
  2. Naredbe iskre ljuske
  3. Najbolji C sastavljači
  4. Vrste algoritama
  5. Faktorski program u JavaScript-u
  6. Vodič za popis naredbi Unix Shell
  7. Vrste oblika u reakciji s primjerima

Kategorija: