Rekursio Pythonissa
Termi rekursio voidaan määritellä prosessiksi, jossa määritellään jotain itsestään. Yksinkertaisesti sanottuna se on prosessi, jossa funktio kutsuu itseään suoraan tai epäsuorasti.
Rekursion käytön edut
- Monimutkainen funktio voidaan jakaa pienempiin osaongelmiin käyttämällä rekursiota.
- Sekvenssien luominen on yksinkertaisempaa rekursion avulla kuin minkä tahansa sisäkkäisen iteroinnin käyttäminen.
- Rekursiiviset funktiot tekevät koodista yksinkertaisen ja tehokkaan.
Rekursion käytön haitat
- Rekursiiviset puhelut vievät paljon muistia ja aikaa, mikä tekee käytöstä kallista.
- Rekursiivisten funktioiden virheenkorjaus on haastavaa.
- Rekursion taustalla olevia perusteluja voi joskus olla vaikea miettiä.
Syntaksi:
def func(): <-- | | (recursive call) | func() ----
Esimerkki 1: Fibonacci-sekvenssi on kokonaislukujono 0, 1, 1, 2, 3, 5, 8….
Python 3
# Program to print the fibonacci series upto n_terms> # Recursive function> def> recursive_fibonacci(n):> > if> n <> => 1> :> > return> n> > else> :> > return> (recursive_fibonacci(n> -> 1> )> +> recursive_fibonacci(n> -> 2> ))> n_terms> => 10> # check if the number of terms is valid> if> n_terms <> => 0> :> > print> (> 'Invalid input ! Please input a positive value'> )> else> :> > print> (> 'Fibonacci series:'> )> for> i> in> range> (n_terms):> > print> (recursive_fibonacci(i))> |
Lähtö
Fibonacci series: 0 1 1 2 3 5 8 13 21 34
Esimerkki 2: Factorial 6 on merkitty 6! = 1*2*3*4*5*6 = 720.
Python 3
# Program to print factorial of a number> # recursively.> # Recursive function> def> recursive_factorial(n):> > if> n> => => 1> :> > return> n> > else> :> > return> n> *> recursive_factorial(n> -> 1> )> # user input> num> => 6> # check if the input is valid or not> if> num <> 0> :> > print> (> 'Invalid input ! Please enter a positive number.'> )> elif> num> => => 0> :> > print> (> 'Factorial of number 0 is 1'> )> else> :> > print> (> 'Factorial of number'> , num,> '='> , recursive_factorial(num))> |
Lähtö
Factorial of number 6 = 720
Mikä on Tail-Recursion?
Ainutlaatuinen rekursiotyyppi, jossa funktion viimeinen proseduuri on rekursiivinen kutsu. Rekursio voidaan automatisoida pois suorittamalla pyyntö nykyisessä pinokehyksessä ja palauttamalla tulos uuden pinokehyksen luomisen sijaan. Kääntäjä voi optimoida häntärekursion, mikä tekee siitä paremman kuin ei-häntärekursiiviset funktiot.
Onko mahdollista optimoida ohjelmaa käyttämällä häntärekursiivista funktiota ei-tail-rekursiivisen funktion sijaan?
Kun otetaan huomioon alla annettu funktio n:n kertoimen laskemiseksi, voidaan havaita, että funktio näyttää aluksi häntärekursiiviselta, mutta se on ei-häntärekursiivinen funktio. Jos tarkkailemme tarkkaan, voimme nähdä, että Recur_facto(n-1):n palauttama arvo on käytössä Recur_facto(n):ssä, joten Recur_facto(n-1):n kutsu ei ole viimeinen asia, jonka Recur_facto(n) tekee.
Python 3
# Program to calculate factorial of a number> # using a Non-Tail-Recursive function.> # non-tail recursive function> def> Recur_facto(n):> > > if> (n> => => 0> ):> > return> 1> > > return> n> *> Recur_facto(n> -> 1> )> > # print the result> print> (Recur_facto(> 6> ))> |
Lähtö
720
Voimme kirjoittaa annetun funktion Recur_facto tail-rekursiivisena funktiona. Ajatuksena on käyttää yhtä argumenttia lisää ja toisessa argumentissa otetaan huomioon faktoriaalin arvo. Kun n saavuttaa 0:n, palauta halutun luvun kertoimen lopullinen arvo.
Python 3
# Program to calculate factorial of a number> # using a Tail-Recursive function.> # A tail recursive function> def> Recur_facto(n, a> => 1> ):> > > if> (n> => => 0> ):> > return> a> > > return> Recur_facto(n> -> 1> , n> *> a)> > # print the result> print> (Recur_facto(> 6> ))> |
Lähtö
720
