Z enostavnimi besedami je rekurzija način reševanja problema s samim klicem funkcije, beseda ' rekurzivno 'Izvira iz latinskega glagola' ponoviti ”, Kar pomeni nekaj predelati. To počne rekurzivna funkcija, ki vedno znova ponovi isto stvar, tj. Se prikliče. V tem članku bomo spoznali rekurzijo v pythonu. V tem blogu so zajete teme:
- Kaj je rekurzija v Pythonu?
- Pogoj prenehanja
- Pythonova meja ponovitve
- Splošni seznami z rekurzijo
- Prednosti rekurzije
- Slabosti rekurzije
Kaj je rekurzija v Pythonu?
Rekurzija je postopek določanja samega sebe. Vemo, da lahko v Pythonu katera koli funkcija pokliče katero koli drugo funkcijo, funkcija lahko pokliče tudi samo sebe. Te vrste funkcij, ki se kličejo, dokler določen pogoj ni izpolnjen, se imenujejo rekurzivne funkcije.
vzemimo si nekaj primerov, da ugotovimo, kako to deluje. Če dobite pozitivno celo število n, bi bil faktor.
- n! = n * (n-1) * (n-2) in tako naprej.
- 2! = 2 * (2-1)
- ena! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Zamenjava zgornjih vrednosti bo povzročila naslednji izraz
- 4! = 4 * 3 * 2 * 1
Moramo definirati funkcijo, ki omogoča recimo dejstvo (n), ki za svoj parameter vzame pozitivno celo število ali 0 in vrne n-ti faktorijel. Kako lahko to storimo z uporabo rekurzije?
Poglejmo, za to z uporabo rekurzije moramo preučiti naslednjo enačbo
n! = n. (n-1). (n-2) & hellip3.2.1
povratne številke celoštevilčnega pitona
n! = n. (n-1)! # zgornjo izjavo lahko napišemo kot v tej vrstici
Zdaj tukaj, če kot parameter prenesemo 2, bomo dobili:
2! = 2,1! = 2
Podobno, če opravimo 1, bomo dobili:
ena! = 1,0! = 1
Če pa preidemo 0, se pokvari
0! = 0. (- 1)! in tukaj faktorijel za -1 ni definiran, zato to deluje samo za vrednosti> 0
Torej moramo napisati dva primera
1. n! = n. (n-1)! če je n> = 1
2. 1, če je n = 0
To je popolna rešitev za vsa pozitivna cela števila in 0.
Pogoj prenehanja
Rekurzivna funkcija mora izpolniti pomemben pogoj za zaključek. Ko se premaknemo k stanju, ko je težavo mogoče rešiti brez nadaljnje rekurzije, se rekurzivna funkcija zaključi in problem zmanjša na manjše pod korake. Rekurzija se lahko konča v neskončni zanki, če pogoj prekinitve v klicih ni izpolnjen.
Faktorski pogoji:
- faktorijel od n = n * (n-1), če je n večji od 1.
- 1, če je n = 0
Zgornje faktorske pogoje bomo pretvorili v python kodo:
def fact (n): če je n == 1: vrni n else: vrni n * dejstvo (n-1)
Vzemimo primer, recimo, da želimo najti faktorje 4:
fact (4) #this bo vrnil 4 * fact (3) in tako naprej, dokler n == 1.
Izhod: 24.
Zaradi enostavnosti in jasnosti se pogosto uporablja kot primer za rekurzijo. Reševanje manjših primerov problema na vsakem koraku, ki ga je v računalništvu poimenoval kot rekurzija.
Pythonova meja ponovitve
V nekaterih jezikih lahko ustvarite neskončno rekurzivno zanko, vendar v Pythonu obstaja omejitev rekurzije. Če želite preveriti omejitev, zaženite naslednjo funkcijo iz modula sys. kar bo dalo mejo rekurzijskega niza za python.
je sas programski jezik
uvoz sys sys.getrecursionlimit ()
Izhod: 1000
Omejitev lahko spremenite tudi s pomočjo funkcijesetrecursionlimit () modula sys v skladu z vašo zahtevo. Zdaj pa ustvarimo funkcijo, ki se sama rekurzivno kliče, dokler ne preseže omejitve, in preveri, kaj se zgodi:
def rekurzivno (): rekurzivno (), če je __name__ == '__main__': rekurzivno ()
Če zaženete zgornjo kodo, boste dobili izjemo med izvajanjem: RuntimeError: presežena je največja globina rekurzije. Python vam preprečuje ustvarjanje funkcije, ki se konča v neskončni rekurzivni zanki.
Splošni seznami z rekurzijo
Druge stvari, ki jih lahko počnete z uporabo rekurzije, razen za to, da recimo želite ustvariti eno s seznama, ki je ugnezden, lahko to storite s spodnjo kodo:
def poravnati (a_list, flat_list = none): če flat_list ni nič: flat_list = [] za element na a_list: if isinstance (item, list): sploščiti (item, flat_list) else: flat_list.append (item) return flat_list if __name__ == '__main__': ugnezdeni = [1,2,3, [4,5], 6] x = poravnaj (ugnezdi) print (x)
Izhod: [1,2,3,4,5,6]
Zagon zgornje kode bo povzročil en seznam namesto celoštevilčnega seznama, ki vsebuje celoštevilčni seznam, ki smo ga uporabili kot vhod. Enako lahko storite tudi na druge načine, Python ima nekaj, kar se imenuje itertools.chain (), lahko preverite kodo, ki se uporablja za ustvarjanje funkcijske verige (), drugačen pristop je narediti isto stvar kot mi.
Prednosti rekurzije
Koda je čista in elegantna v rekurzivni funkciji.
Sestavljeno nalogo je mogoče razbiti na preprostejše podteže z uporabo rekurzije.
Ustvarjanje zaporedja je z rekurzijo lažje kot z uporabo neke ugnezdene ponovitve.
Slabosti rekurzije
Slediti logiki rekurzivne funkcije je včasih težko.
Rekurzivni klici so dragi (neučinkoviti), saj trajajo veliko pomnilnika in časa.
Rekurzivne funkcije je težko odpraviti.
V tem članku smo videli, kaj je rekurzija in kako lahko iz stavka problema razvijemo rekurzivne funkcije, kako matematično lahko definiramo stavek problema. Rešili smo problem s faktorijem in ugotovili pogoje, potrebne za iskanje faktorijev, iz katerih smo lahko te pogoje pretvorili v python kodo, da bi dobili razumevanje, kako deluje rekurzija. Mislim, da je lepo, da ima Python vgrajeno omejitev za rekurzijo, da razvijalcem preprečuje ustvarjanje slabo zgrajenih rekurzivnih funkcij. Pomembno je opaziti, da je težko odpraviti napake pri rekurziji, saj funkcija nenehno kliče sama.