Tässä opetusohjelmassa opit luomaan rekursiivisen funktion (toiminto, joka kutsuu itseään).
Mikä on rekursio?
Rekursio on prosessi, jossa määritellään jotain itsestään.
Fyysisen maailman esimerkki olisi sijoittaa kaksi rinnakkaista peiliä vastakkain. Mikä tahansa niiden välissä oleva esine heijastuu rekursiivisesti.
Python-rekursiivinen toiminto
Pythonissa tiedämme, että funktio voi kutsua muita toimintoja. On jopa mahdollista, että toiminto kutsuu itseään. Tämän tyyppisiä rakenteita kutsutaan rekursiivisiksi funktioiksi.
Seuraava kuva näyttää kutsutun rekursiivisen toiminnon toiminnan recurse.
Rekursiivinen toiminto Pythonissa
Seuraava on esimerkki rekursiivisesta funktiosta kokonaisluvun kertoimen löytämiseksi.
Luvun kerroin on kaikkien kokonaislukujen tulo luvusta 1 tähän lukuun. Esimerkiksi kerroin 6 (merkitty 6: ksi!) On 1 * 2 * 3 * 4 * 5 * 6 = 720.
Esimerkki rekursiivisesta funktiosta
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))
Tuotos
3: n kerroin on 6
Yllä olevassa esimerkissä factorial()se on rekursiivinen funktio, kuten se itse kutsuu.
Kun kutsumme tätä funktiota positiivisella kokonaisluvulla, se kutsuu itseään rekursiivisesti vähentämällä lukua.
Kukin funktio kertoo luvun ja sen alapuolella olevan luvun faktorialan, kunnes se on yhtä suuri. Tämä rekursiivinen puhelu voidaan selittää seuraavissa vaiheissa.
kerroin (3) # 1. puhelu 3 3 * kertoimella (2) # 2. puhelu 2 3 * 2 * kertoimella (1) # 3. puhelu 1 3 * 2 * 1 # paluu kolmannesta puhelusta numerona = 1 3 * 2 # paluu toisesta puhelusta 6 # paluu ensimmäisestä puhelusta
Katsotaan kuvaa, joka näyttää askel askeleelta prosessin siitä, mitä tapahtuu:
Rekursiivisen tekijäfunktion työskentely
Rekursiomme päättyy, kun lukumäärä pienenee arvoon 1. Tätä kutsutaan perusedellytykseksi.
Jokaisella rekursiivisella funktiolla on oltava perusedellytys, joka lopettaa rekursio, tai muuten toiminto kutsuu itseään loputtomasti.
Python-tulkki rajoittaa rekursiosyvyyttä välttääkseen loputtomat rekursiot, mikä johtaa pinon ylivuotoon.
Oletusarvoisesti rekursio on enintään 1000. Jos raja ylitetään, se johtaa RecursionError. Katsotaanpa yhtä tällaista ehtoa.
def recursor(): recursor() recursor()
Tuotos
Seuranta (viimeisin puhelu viimeisin): Tiedosto "", rivi 3, tiedostossa "", rivi 2, tiedostossa "", rivi 2, tiedostossa "", rivi 2, tiedostossa "", rivi 2, rivillä (edellinen rivi toistettu vielä 996 kertaa) ) RecursionError: suurin rekursiosyvyys ylitetty
Rekursioedut
- Rekursiiviset toiminnot tekevät koodista tyylikkään ja puhtaan.
- Monimutkainen tehtävä voidaan jakaa yksinkertaisempiin alaongelmiin rekursiota käyttämällä.
- Sekvenssin luominen on helpompaa rekursiolla kuin sisäkkäisen iteraation käyttäminen.
Rekursioiden haitat
- Joskus rekursio-logiikkaa on vaikea noudattaa.
- Rekursiiviset puhelut ovat kalliita (tehoton), koska ne vievät paljon muistia ja aikaa.
- Rekursiivisia toimintoja on vaikea korjata.
