Mikä on rekursiivinen toiminto?
Toiminto soittaa itselleen uudestaan ja uudestaan, kunnes se täyttää rekursiivisen ehdon. Rekursiointitoiminto hajottaa ongelman pienemmiksi ongelmiksi ja kutsuu oman logiikansa pienemmän ongelman ratkaisemiseksi. Tätä tekniikkaa kutsutaan jakamaan ja valloittamaan. Sitä käytetään matematiikassa ja tietotekniikan alalla.
Rekursiivinen toiminto sisältää perus- tai päätelaatikon ja rekursiivisen tapauksen. Perustapauksessa voit harkita suurimman ongelman ratkaisemista ja rekursiivinen tapa jakaa ongelman pienempiin osiin, kunnes se saavuttaa tason, jossa se voidaan helposti ratkaista. Rekursiivinen tapaus voi antaa tuloksen tai se voi kutsua itsensä uudelleen jakamaan ongelman edelleen. Aina kun ongelma hajoaa pienemmäksi ongelmaksi, toiminto, johon kutsutaan rekursiivisesti, tallentaa puhelun tilan ja odottaa tulosta itseltään ongelman hajottamisen jälkeen.
Rekursiivinen toiminto Pythonissa
Rekursion käsite pysyy samana Pythonissa. Toiminto kutsuu itse jakamaan ongelman pienemmiksi ongelmiksi. Yksinkertaisin esimerkki, jonka voimme ajatella rekursiosta, olisi luvun tekijän löytäminen.
Oletetaan, että meidän on löydettävä lukumäärä 5 => 5! (Ongelmamme)
Löytää 5! ongelma voidaan hajottaa pienemmiksi 5! => 5 x 4!
Joten saada 5! Meidän on löydettävä 4! ja kertoa se 5: llä.
Jatkakaamme ongelman jakamista
5! = 4! x 5
4! = 3! x 4
3! = 3 x 2!
2! = 2 x 1!
1! = 1
Kun se saavuttaa pienimmän osan, ts. Saadaksesi kertoimen 1, voimme palauttaa tuloksen
Otetaan esimerkki pseudokoodista: -
Algoritmi tekijälle
Katsotaanpa algoritmi tekijöille:
function get_factorial( n ):
if n < 2:
return 1
else:
return get_factorial(n -1)
Toimintopuhelut
Oletetaan, että löydämme kertoimen 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
Lopputulos on 120, josta aloitimme toiminnon suorittamisen. Rekursiointitoiminto pysähtyy, kun lukumäärä on niin pienentynyt, että tulos voidaan saada.
- Ensimmäinen puhelu, josta saadaan kerroin 5, johtaa rekursiiviseen tilaan, jossa se lisätään pinoon ja toinen puhelu soitetaan sen jälkeen, kun numero on vähennetty 4: ksi.
- Tämä toisto jatkaa soittamista ja ongelman jakamista pienemmiksi palasiksi, kunnes se saavuttaa perustilan.
- Perusedellytys on tässä, kun luku on 1.
- Jokaisella rekursiivisella toiminnolla on oma rekursiivinen ehto ja perustila.
Hyödyt ja haitat Python-rekursiivisesta toiminnosta
- Rekursion toteutus on sellainen, että se ei tee mitään laskelmia ennen kuin saavuttaa perustilan.
- Perusolosuhteisiin pääsemiseksi muistia saattaa loppua.
- Laajassa ongelmassa, jossa voi olla miljoona askelta tai voimme sanoa miljoonan ohjelman toistokertoja, saattaa aiheutua muistivirheestä tai segmentointivirheestä.
- 1000000! = 1000000 * 999999! =?
- Rekursio on erilainen kuin iteraatio, se ei ole suurempi kuin iteratiivinen menetelmä.
- Eri kielillä on erilaisia optimointeja rekursiota varten.
- Monilla kielillä iteratiivinen menetelmä toimisi paremmin kuin rekursio.
- Jokaisella kielellä on joitain rajoituksia rekursion syvyydelle, joita saatat kohdata ratkaiseessasi suuria ongelmia.
- Joskus on vaikea ymmärtää rekursion monimutkaisia ongelmia, kun taas iterointi on melko yksinkertaista.
Jotkut plussat
- Joissakin tapauksissa rekursio on kätevä ja nopeampi tapa käyttää.
- Hyvin hyödyllistä puun liikkumisessa ja binaarisessa haussa.
Python-koodi - Rekursio vs. toisto
Ymmärsimme, mikä on rekursio ja miten se toimii Pythonissa, koska tiedämme, että kaikilla kielillä on erilainen rekursion toteutus muistiin ja laskennallisiin optimointeihin. Voi olla tapaus, jossa iterointi olisi nopeampaa kuin rekursio.
Tässä verrataan sekä rekursiota että iteraatiomenetelmää nähdäksesi kuinka Python toimii molemmissa tapauksissa.
1. Faktoriaalin rekursiokoodi
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. Tekijäongelma iteraation avulla (silmukka)
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. Tulosten tulostaminen
print(get_recursive_factorial(6))
print(get_iterative_factorial(6))
lähtö:
Kuten näemme, molemmat antavat saman tuloksen, kuin olemme kirjoittaneet saman logiikan. Täällä emme näe eroja toteutuksessa.
Lisäämme aikakoodin saadaksesi lisätietoja rekursion ja iteraation suorituksesta Pythonissa.
Tuomme “aika” -kirjaston ja tarkistamme, minkä ajanjakson rekursio ja toisto vie tuloksen palauttamiseksi.
4. Koodi aikalaskelmalla
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))
Teemme toistuvia suorituksia, joilla on eri arvo faktoriaalille, ja näemme tulokset. Alla olevat tulokset voivat vaihdella koneittain. Olemme käyttäneet MacBook Prota 16 Gt RAM i7.
Käytämme Python 3.7: tä suorittamiseen
Tapaus 1: - Factorial of 6:
Tapaus 2: Factorial of 50:
Tapaus 3: 100: n tekijä
Tapaus 4: 500: n tekijä
Tapaus 5: Factorial of 1000:
Olemme analysoineet molemmat menetelmät eri ongelmassa. Lisäksi molemmat ovat suorittaneet vastaavasti paitsi tapauksen 4.
Tapauksessa 5 saimme virheen tekeessämme sitä rekursiolla.
Python sai rajoituksen enimmäissyvyydestä, johon voit mennä rekursiolla, mutta sama ongelma, jonka minä pystyin ratkaisemaan iteraatiolla.
Pythonilla on rajoituksia ylivuodon ongelmaa vastaan. Pythonia ei ole optimoitu häntärekursiota varten, ja hallitsematon rekursio aiheuttaa pinon ylivuodon.
“Sys.getrecursionlimit ()” -toiminto kertoisi rekursion rajan.
Rekursiorajaa voidaan muuttaa, mutta ei suositella, se voi olla vaarallinen.
Johtopäätös - Python-rekursiivinen toiminto
- Rekursio on kätevä ratkaisu joihinkin ongelmiin, kuten puiden kulkemiseen ja muihin ongelmiin.
- Python ei ole toimiva ohjelmointikieli, ja voidaan nähdä, että rekursiopino ei ole optimoitu verrattuna iteraatioon.
- Meidän pitäisi käyttää iteraatiota algoritmeissamme, koska se on optimoitu paremmin Pythonissa ja antaa sinulle paremman nopeuden.
Suositellut artikkelit
Tämä on opas Pythonin rekursiiviseen toimintaan. Tässä keskustellaan siitä, mikä on rekursiivinen toiminto, Pythonin rekursiivinen toiminto, tekijäalgoritmi jne. Voit myös käydä läpi muut ehdotetut artikkelimme saadaksesi lisätietoja -
- Tehtaalla Pythonissa
- Spark Shell -komennot
- Parhaat C-kääntäjät
- Algoritmien tyypit
- Factorial Program in JavaScript
- Opas Unix-kuorikomentojen luetteloon
- Reagoi esimerkkeihin