Jednostavnim riječima, rekurzija je način rješavanja problema samim pozivom funkcije, Riječ ' ponavljajući 'Potječe od latinskog glagola' ponoviti ”, Što znači ponoviti nešto. To radi rekurzivna funkcija, ponavlja istu stvar iznova i iznova, tj. Podsjeća na sebe. U ovom ćemo članku naučiti o rekurziji u pythonu. Slijede teme obrađene na ovom blogu:
- Što je rekurzija u Pythonu?
- Uvjet raskida
- Pythonova granica rekurzije
- Poravnavanje popisa s rekurzijom
- Prednosti rekurzije
- Mane rekurzije
Što je rekurzija u Pythonu?
Rekurzija je postupak određivanja nečega u smislu samog sebe. Znamo da u Pythonu svaka funkcija može pozvati bilo koju drugu funkciju, funkcija također može pozvati sebe. Te vrste funkcija koje se same pozivaju dok određeni uvjet ne bude zadovoljen nazivaju se rekurzivnim funkcijama.
uzmimo nekoliko primjera da vidimo kako to funkcionira. Ako vam se da pozitivni cijeli broj n, faktorijel bi bio.
- n! = n * (n-1) * (n-2) i tako dalje.
- 2! = 2 * (2-1)
- jedan! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Zamjena gornjih vrijednosti rezultirat će sljedećim izrazom
- 4! = 4 * 3 * 2 * 1
Moramo definirati funkciju koja dopušta rec činjenicu (n) koja uzima pozitivni cijeli broj ili 0 kao svoj parametar i vraća n-ti faktorijel, kako to možemo učiniti pomoću rekurzije?
Da vidimo, da bismo to učinili pomoću rekurzije moramo ispitati sljedeću jednadžbu
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! # gornju izjavu možemo prepisati kao u ovaj redak
Sad ako proslijedimo 2 kao parametar, dobit ćemo:
java pronaći najvišu vrijednost u polju
2! = 2,1! = 2
Slično tome, ako prođemo 1 dobit ćemo:
jedan! = 1,0! = 1
Ali ako prođemo 0, pukne
0! = 0. (- 1)! a ovdje faktorijel za -1 nije definiran pa ovo vrijedi samo za vrijednosti> 0
Moramo napisati dva slučaja
1. n! = n. (n-1)! ako je n> = 1
2. 1 ako je n = 0
Ovo je cjelovito rješenje za sve pozitivne cijele brojeve i 0.
Uvjet raskida
Rekurzivna funkcija mora ispuniti važan uvjet za završetak. Krećući se prema stanju u kojem se problem može riješiti bez daljnje rekurzije, rekurzivna funkcija će se završiti, umanjujući problem na manje podkorake. Rekurzija može završiti u beskonačnoj petlji ako u pozivima nije zadovoljen uvjet prekida.
Faktorski uvjeti:
- faktorijel od n = n * (n-1) sve dok je n veći od 1.
- 1 ako je n = 0
Gornje faktorske uvjete pretvorit ćemo u python kôd:
def fact (n): ako je n == 1: return n else: return n * fact (n-1)
Uzmimo primjer, recimo da želimo pronaći faktor od 4:
fact (4) # ovo će vratiti činjenicu 4 * (3) i tako dalje dok n == 1.
Izlaz: 24
Tako se često koristi kao primjer za rekurziju zbog svoje jednostavnosti i jasnoće. Rješavanje manjih slučajeva problema u svakom koraku koji je u računalnoj znanosti nazvao rekurzijom.
Pythonova granica rekurzije
U nekim jezicima možete stvoriti beskonačnu rekurzivnu petlju, ali u Pythonu postoji ograničenje rekurzije. Da biste provjerili ograničenje, pokrenite sljedeću funkciju iz sys modula. što će dati granicu rekurzijskog skupa za python.
uvoz sys sys.getrecursionlimit ()
Izlaz: 1000
Ograničenje također možete promijeniti pomoću funkcijesetrecursionlimit () modula sys prema vašem zahtjevu. Sada kreirajmo funkciju koja se rekurzivno poziva dok ne prekorači ograničenje i provjeri što se događa:
def rekurzivno (): rekurzivno () ako je __name__ == '__main__': rekurzivno ()
Ako pokrenete gornji kôd, dobit ćete runtime iznimku: RuntimeError: premašena je maksimalna dubina rekurzije. Python vas sprječava u stvaranju funkcije koja završava u beskonačnoj rekurzivnoj petlji.
Poravnavanje popisa s rekurzijom
Ostale stvari koje možete raditi pomoću rekurzije, osim faktora, recimo da želite stvoriti singl s popisa koji je ugniježđen, to se može učiniti pomoću donjeg koda:
def poravnati (a_list, flat_list = none): ako flat_list nijedan: flat_list = [] za stavku na a_listu: if isinstance (item, list): spljoštiti (item, flat_list) else: flat_list.append (item) return flat_list if __name__ == '__main__': ugniježđeno = [1,2,3, [4,5], 6] x = poravnati (ugniježđeno) ispis (x)
Izlaz: [1,2,3,4,5,6]
Pokretanje gornjeg koda rezultirat će jednim popisom umjesto cjelovitog popisa koji sadrži cjelobrojni popis koji smo koristili kao ulaz. Isto možete učiniti i na druge načine, Python ima nešto što se naziva itertools.chain (), možete provjeriti kod koji se koristi za stvaranje lanca funkcija (), drugačiji je pristup raditi istu stvar kao i mi.
Prednosti rekurzije
Kôd je čist i elegantan u rekurzivnoj funkciji.
Složeni zadatak može se rastaviti na jednostavnije pod-probleme pomoću rekurzije.
Generiranje sekvence lakše je s rekurzijom nego korištenjem neke ugniježđene iteracije.
Mane rekurzije
Slijediti logiku koja stoji iza rekurzivne funkcije ponekad može biti teško.
Rekurzivni pozivi skupi su (neučinkoviti) jer zauzimaju puno memorije i vremena.
Teško je otkloniti pogreške u rekurzivnim funkcijama.
U ovom smo članku vidjeli što je rekurzija i kako iz izraza problema možemo razviti rekurzivne funkcije, kako matematički mogu definirati iskaz problema. Riješili smo problem s faktorom i pronašli uvjete potrebne za pronalazak faktora iz kojih smo uspjeli pretvoriti te uvjete u python kôd dajući vam razumijevanje kako rekurzija djeluje. Mislim da je lijepo što Python ima ugrađeno ograničenje za rekurziju kako bi spriječio programere da kreiraju loše konstruirane rekurzivne funkcije. Jedna važna stvar koju treba primijetiti jest da je rekurziju teško otkloniti pogreške jer se funkcija neprestano poziva.