Python rekurzija (rekurzivna funkcija)

V tej vadnici se boste naučili ustvariti rekurzivno funkcijo (funkcijo, ki se sama pokliče).

Kaj je rekurzija?

Rekurzija je postopek opredelitve nečesa kot samega sebe.

Primer fizičnega sveta bi bil postavitev dveh vzporednih ogledal drug proti drugemu. Vsak predmet vmes bi se odseval rekurzivno.

Python rekurzivna funkcija

V Pythonu vemo, da lahko funkcija pokliče druge funkcije. Funkcija je lahko tudi sama poklicana. Te vrste konstruktov imenujemo rekurzivne funkcije.

Naslednja slika prikazuje delovanje imenovane rekurzivne funkcije recurse.

Rekurzivna funkcija v Pythonu

Sledi primer rekurzivne funkcije za iskanje faktorijela celega števila.

Faktor na število je zmnožek vseh celih števil od 1 do tega števila. Na primer, faktorijel 6 (označen kot 6!) Je 1 * 2 * 3 * 4 * 5 * 6 = 720.

Primer rekurzivne funkcije

 def factorial(x): """This is a recursive function to find the factorial of an integer""" if x == 1: return 1 else: return (x * factorial(x-1)) num = 3 print("The factorial of", num, "is", factorial(num))

Izhod

 Faktorial 3 je 6

V zgornjem primeru factorial()je rekurzivna funkcija, kot se sama pokliče.

Ko to funkcijo pokličemo s pozitivnim celim številom, se bo rekurzivno poklicala z zmanjšanjem števila.

Vsaka funkcija pomnoži število s faktorjelom števila pod seboj, dokler ni enako enaki. Ta rekurzivni klic je mogoče razložiti v naslednjih korakih.

 factorial (3) # 1. klic s 3 3 * factorial (2) # 2. klic z 2 3 * 2 * faktorijem (1) # 3. klic z 1 3 * 2 * 1 # vrnitev s 3. klica kot številka = 1 3 * 2 # vrnitev iz 2. klica 6 # vrnitev iz 1. klica

Oglejmo si sliko, ki prikazuje postopni postopek dogajanja:

Delovanje rekurzivne faktorjske funkcije

Naša rekurzija se konča, ko se število zmanjša na 1. To se imenuje osnovni pogoj.

Vsaka rekurzivna funkcija mora imeti osnovni pogoj, ki zaustavi rekurzijo, sicer pa se funkcija neskončno pokliče.

Tolmač Python omejuje globino rekurzije, da se izogne ​​neskončnim rekurzijam, kar povzroči prelivanje skladov.

Privzeto je največja globina rekurzije 1000. Če je meja presežena, je rezultat RecursionError. Poglejmo en tak pogoj.

 def recursor(): recursor() recursor()

Izhod

 Sledenje (zadnji zadnji klic): Datoteka "", vrstica 3, v datoteki "", vrstica 2, v datoteki "", vrstica 2, v datoteki "", vrstica 2, v (prejšnja vrstica ponovljena še 996 krat ) RecursionError: presežena največja globina rekurzije

Prednosti rekurzije

  1. Z rekurzivnimi funkcijami je koda videti čista in elegantna.
  2. Kompleksno nalogo lahko z uporabo rekurzije razdelimo na preprostejše podteže.
  3. Ustvarjanje zaporedja je z rekurzijo lažje kot z uporabo neke ugnezdene ponovitve.

Slabosti rekurzije

  1. Včasih je težko slediti logiki rekurzije.
  2. Rekurzivni klici so dragi (neučinkoviti), saj vzamejo veliko pomnilnika in časa.
  3. Rekurzivne funkcije je težko odpraviti.

Zanimive Članki...