Vienkārši sakot, rekursija ir veids, kā atrisināt problēmu, liekot pašai izsaukt funkciju. Vārds “ rekursīvs ”Cēlies no latīņu darbības vārda“ atkārtoties ”, Kas nozīmē kaut ko pārtaisīt. To veic rekursīvā funkcija, tā atkal un atkal pārstrādā to pašu, t.i., pati sevi atsauc. Šajā rakstā mēs uzzināsim par rekursiju pitonā. Šajā emuārā apskatītas šādas tēmas:
- Kas ir rekursija Python?
- Izbeigšanas nosacījums
- Python rekursijas ierobežojums
- Sarakstu saplacināšana ar rekursiju
- Rekursijas priekšrocības
- Rekursijas trūkumi
Kas ir rekursija Python?
Rekursija ir process, kurā kaut ko nosaka pati par sevi. Mēs zinām, ka Pitonā jebkura funkcija var izsaukt jebkuru citu funkciju, funkcija var saukt arī sevi. Šāda veida funkcijas, kas sevi izsauc, kamēr nav izpildīts noteiktais nosacījums, tiek sauktas par rekursīvām funkcijām.
Paņemsim dažus piemērus, lai redzētu, kā tas darbojas. Ja jums tiek piešķirts pozitīvs vesels skaitlis n, faktoriālā vērtība būtu.
- n! = n * (n-1) * (n-2) un tā tālāk.
- 2! = 2 * (2-1)
- viens! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Aizstājot iepriekš minētās vērtības, tiks iegūta šāda izteiksme
- 4! = 4 * 3 * 2 * 1
Mums ir jādefinē funkcija, ļaujot pateikt faktu (n), kura parametrs ir pozitīvs vesels skaitlis vai 0 un atgriež n-to faktoriāli. Kā mēs to varam izdarīt, izmantojot rekursiju?
Apskatīsim, lai to izdarītu, izmantojot rekursiju, mums jāpārbauda šāds vienādojums
n! = n. (n-1). (n-2) & hellip3.2.1
n! = n. (n-1)! # mēs varam pārrakstīt iepriekš minēto paziņojumu kā šajā rindā
Tagad šeit, ja mēs izturēsim 2 kā parametru, mēs saņemsim:
2! = 2,1! = 2
atšķirība starp pārslodzi un pārsvaru c ++
Līdzīgi, ja mēs izturēsim 1, mēs iegūsim:
viens! = 1,0! = 1
Bet, ja mēs nokārtojam 0, tas saplīst
0! = 0. (- 1)! un šeit koeficients -1 nav definēts, tāpēc tas darbojas tikai vērtībām> 0
Tāpēc mums ir jāraksta divi gadījumi
1. n! = n. (n-1)! ja n> = 1
2. 1, ja n = 0
Tas ir pilnīgs risinājums visiem pozitīvajiem skaitļiem un 0.
Izbeigšanas nosacījums
Rekurzīvajai funkcijai ir jāizpilda svarīgs nosacījums, lai to pārtrauktu. Pārejot uz nosacījumu, kurā problēmu var atrisināt bez turpmākas rekursijas, tiks pārtraukta rekursīvā funkcija, līdz minimumam samazinot problēmu mazākās apakšpakāpēs. Rekursija var nonākt bezgalīgā ciklā, ja zvanu laikā nav izpildīts pārtraukšanas nosacījums.
Faktoriālie nosacījumi:
- faktori n = n * (n-1), kamēr n ir lielāks par 1.
- 1, ja n = 0
Mēs pārveidosim iepriekš minētos faktora nosacījumus pitona kodā:
def fakts (n): ja n == 1: atgriež n citu: atgriež n * faktu (n-1)
Ņemsim piemēru, teiksim, ka mēs vēlamies atrast faktoriālu no 4:
fakts (4) # šis atgriezīs 4 * faktu (3) un tā tālāk, līdz n == 1.
Izeja: 24
Tās vienkāršības un skaidrības dēļ to tik bieži izmanto kā rekursijas piemēru. Mazāku problēmu gadījumu risināšana katrā solī, ko tā sauca par rekursiju datorzinātnēs.
Python rekursijas ierobežojums
Dažās valodās jūs varat izveidot bezgalīgu rekursīvu cilpu, taču Python ir rekursijas ierobežojums. Lai pārbaudītu limitu, palaidiet šo funkciju no sys moduļa. kas dos pitonam iestatītās rekursijas robežu.
kas ir džits java
importēt sys sys.getrecursionlimit ()
Izeja: 1000
Varat arī mainīt limitu, izmantojot sys moduļa funkcijasetrecursionlimit () atbilstoši jūsu prasībām. Tagad izveidosim funkciju, kas sevi sauc rekursīvi, līdz tā pārsniedz limitu un pārbauda, kas notiek:
def rekursīvs (): rekursīvs () ja __nosaukums__ == '__main__': rekursīvs ()
Izpildot iepriekš minēto kodu, tiks parādīts izpildlaika izņēmums: RuntimeError: pārsniegts maksimālais rekursijas dziļums. Python neļauj jums izveidot funkciju, kas nonāk nebeidzamā rekursīvā lokā.
Sarakstu saplacināšana ar rekursiju
Citas lietas, kuras varat darīt, izmantojot rekursiju, izņemot faktoriāles, pieņemsim, ka vēlaties izveidot vienu no saraksta, kurā ir ligzdas, to var izdarīt, izmantojot tālāk norādīto kodu:
def saplacināt (a_list, flat_list = none): ja flat_list nav: flat_list = [] elementam a_list: ja isinstance (item, list): saplacināt (item, flat_list) cits: flat_list.append (item) atgriezt flat_list ja __name__ == '__main__': ligzdots = [1,2,3, [4,5], 6] x = saplacināt (ligzdots) druka (x)
Izeja: [1,2,3,4,5,6]
Palaidot iepriekš minēto kodu, tiks iegūts viens saraksts, nevis vesels skaitlis, kas satur veselu skaitļu sarakstu, kuru mēs izmantojām kā ievadi. Jūs varat arī darīt to pašu, izmantojot arī citus veidus, Python ir kaut kas tāds kā itertools.chain (), jūs varat pārbaudīt kodu, kas izmantots funkciju ķēdes izveidošanai (), tā ir atšķirīga pieeja darīt to pašu, ko mēs darījām.
Rekursijas priekšrocības
Rekursīvajā funkcijā kods ir tīrs un elegants.
Salikto uzdevumu var sadalīt vienkāršākās apakšproblēmās, izmantojot rekursiju.
Sekvenci ģenerēt ar rekursiju ir vieglāk nekā ar dažu ligzdotu atkārtojumu.
Rekursijas trūkumi
Rekursīvās funkcijas loģikas ievērošana dažreiz var būt sarežģīta.
Rekursīvie zvani ir dārgi (neefektīvi), jo tie aizņem daudz atmiņas un laika.
Rekursīvās funkcijas ir grūti atkļūdot.
Šajā rakstā mēs redzējām, kas ir rekursija un kā mēs varam izstrādāt rekursīvas funkcijas no problēmas paziņojuma, cik matemātiski var definēt problēmas paziņojumu. Mēs atrisinājām faktoriāla problēmu un noskaidrojām nosacījumus, kas nepieciešami, lai atrastu faktorialus, no kuriem mēs šos apstākļus varējām pārveidot par pitona kodu, sniedzot jums izpratni par rekursijas darbību. Manuprāt, tas ir kārtīgi, ka Python ir iebūvēts rekursijas ierobežojums, lai neļautu izstrādātājiem izveidot slikti konstruētas rekursijas funkcijas. Viena svarīga lieta, kas jāpievērš uzmanībai, ir tāda, ka rekursiju ir grūti atkļūdot, jo funkcija turpina sevi saukt.