mikä on rekursio?

rekursio on prosessi, jossa määritellään jokin asia itsensä kannalta.

fyysinen maailma esimerkki olisi sijoittaa kaksi rinnakkaista peiliä vastakkain. Mikä tahansa niiden välissä oleva esine heijastuisi rekursiivisesti.

Pythonin rekursiivinen funktio

Pythonissa tiedetään, että funktio voi kutsua muita funktioita. On jopa mahdollista, että funktio kutsuu itseään. Tällaisia konstruktiotyyppejä kutsutaan rekursiivisiksi funktioiksi.

seuraavassa kuvassa näkyy rekursiivisen funktion recursetoiminta.

Seuraavassa on esimerkki rekursiivisesta funktiosta, jolla etsitään kokonaisluvun faktori.

luvun Faktori on kaikkien kokonaislukujen tulo 1: stä kyseiseen lukuun. Esimerkiksi factorial 6 (merkitään 6!) 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 = 3print("The factorial of", num, "is", factorial(num))

Lähtö

The factorial of 3 is 6

yllä olevassa esimerkissä factorial() on rekursiivinen funktio, kuten se itseään kutsuu.

kun kutsumme tätä funktiota positiivisella kokonaisluvulla, se kutsuu itseään rekursiivisesti vähentämällä lukua.

jokainen funktio kertoo luvun sen alapuolella olevan luvun faktorilla, kunnes se on yhtä suuri kuin yksi. Tämä rekursiivinen kutsu voidaan selittää seuraavissa vaiheissa.

factorial(3) # 1st call with 33 * factorial(2) # 2nd call with 23 * 2 * factorial(1) # 3rd call with 13 * 2 * 1 # return from 3rd call as number=13 * 2 # return from 2nd call6 # return from 1st call

Katsotaanpa kuvaa, joka näyttää vaiheittaisen prosessin siitä, mitä tapahtuu:

rekursio päättyy, kun luku pienenee arvoon 1. Tätä kutsutaan peruskunnoksi.

jokaisella rekursiivisella funktiolla on oltava perusehto, joka pysäyttää rekursion tai muuten funktio kutsuu itseään äärettömäksi.

Python-tulkki rajoittaa rekursion syvyyksiä auttaakseen välttämään äärettömiä rekursioita, jolloin pinon ylivuotoja syntyy.

oletuksena rekursion maksimisyvyys on 1000. Jos raja ylittyy, tuloksena on RecursionError. Katsotaanpa yksi tällainen ehto.

def recursor(): recursor()recursor()

Lähtö

Traceback (most recent call last): File "<string>", line 3, in <module> File "<string>", line 2, in a File "<string>", line 2, in a File "<string>", line 2, in a RecursionError: maximum recursion depth exceeded

rekursion edut

1. rekursiiviset funktiot saavat koodin näyttämään siistiltä ja tyylikkäältä.
2. monimutkainen tehtävä voidaan jakaa yksinkertaisempiin alaongelmiin rekursion avulla.
3. sekvenssin luominen on helpompaa rekursion avulla kuin käyttämällä jotakin sisäkkäistä iteraatiota.

rekursion haitat

1. joskus rekursion taustalla olevaa logiikkaa on vaikea noudattaa.
2. rekursiiviset puhelut ovat kalliita (tehottomia), sillä ne vievät paljon muistia ja aikaa.
3. rekursiivisia funktioita on vaikea debugoida.