Lihtsamalt öeldes on rekursioon viis probleemi lahendamiseks, kutsudes funktsiooni ise üles. korduv ”Pärineb ladina verbist“ korduma ”, Mis tähendab midagi ümber teha. Seda teeb rekursiivne funktsioon, see teeb sama asja uuesti ja uuesti, st tuletab ennast meelde. Selles artiklis tutvume rekursiooniga pythonis. Selles blogis käsitletakse järgmisi teemasid:
- Mis on rekursioon Pythonis?
- Lõpetamise tingimus
- Pythoni rekursioonilimiit
- Rekursiooniga loendite tasandamine
- Rekursiooni eelised
- Rekursiooni puudused
Mis on rekursioon Pythonis?
Rekursioon on protsess, mille käigus määratakse midagi iseenesest. Me teame, et Pythonis võib iga funktsioon kutsuda mis tahes muud funktsiooni, funktsioon võib ka ise helistada. Seda tüüpi funktsioone, mis kutsuvad ennast seni, kuni teatud tingimus pole täidetud, nimetatakse rekursiivseteks funktsioonideks.
võtame paar näidet, et näha, kuidas see töötab. Kui teile antakse positiivne täisarv n, oleks faktoriaal.
- n! = n * (n-1) * (n-2) ja nii edasi.
- 2! = 2 * (2-1)
- üks! = 1
- 0! = 0
- 4! = 4 * 3!
- 3! = 3 * 2!
- 2! = 2 * 1!
Ülaltoodud väärtuste asendamine annab järgmise avaldise
fibonacci c ++ rekursiivne
- 4! = 4 * 3 * 2 * 1
Me peame määratlema funktsiooni, mis võimaldab öelda fakti (n), mille parameetriks on positiivne täisarv või 0 ja tagastatakse n-nda faktoriaal. Kuidas me saame seda teha rekursiooni abil?
Vaatame, et seda teha rekursiooni abil, peame uurima järgmist võrrandit
n! = n. (n-1). (n-2) ja põrgu 3.2.1
n! = n. (n-1)! #me võime ülaltoodud väite ümber kirjutada nagu sellel real
Nüüd, kui me läbime parameetrina 2, saame:
2! = 2,1! = 2
Samamoodi, kui me läbime 1, saame:
üks! = 1,0! = 1
Aga kui me ületame 0, siis see puruneb
0! = 0. (- 1)! ja siin pole faktori väärtuseks -1 määratletud, nii et see töötab ainult väärtuste> 0 korral
Seega peame kirjutama kaks juhtumit
1. n! = n. (n-1)! kui n> = 1
2. 1, kui n = 0
See on kõigi positiivsete täisarvude ja 0 täielik lahendus.
Lõpetamise tingimus
Rekursiivne funktsioon peab lõpetamiseks olema oluline. Liikudes olukorra poole, kus probleemi saab lahendada ilma täiendava rekursioonita, lõpetatakse rekursiivne funktsioon, minimeerides probleemi väiksematesse alamastmetesse. Rekursioon võib lõppeda lõpmatu kontuuriga, kui kõnedes ei ole lõpetamise tingimus täidetud.
Faktorite tingimused:
- faktoriaal n = n * (n-1) seni, kuni n on suurem kui 1.
- 1, kui n = 0
Teisendame ülaltoodud faktori tingimused pythoni koodis:
def fakt (n): kui n == 1: tagastage n muu: tagastage n * fakt (n-1)
Võtame näite, näiteks tahame leida 4 faktori:
fakt (4) # see tagastab 4 * fakti (3) ja nii edasi, kuni n == 1.
Väljund: 24
Seda kasutatakse nii sageli kui ka rekursiooni näitena oma lihtsuse ja selguse tõttu. Väiksemate probleemijuhtude lahendamine igal sammul, mida see nimetas arvutiteaduse rekursiooniks.
Pythoni rekursioonilimiit
Mõnes keeles saate luua lõpmatu rekursiivse tsükli, kuid Pythonis on rekursioonilimiit. Limiidi kontrollimiseks käivitage järgmine funktsioon sys moodulist. mis annab pythoni jaoks määratud rekursiooni piiri.
kuidas luua objektide massiivi
impordi sys sys.getrecursionlimit ()
Väljund: 1000
Piirangut saate muuta ka sys mooduli funktsioonideetrecursionlimit () abil vastavalt teie nõudele. Nüüd loome funktsiooni, mis kutsub ennast rekursiivselt, kuni see ületab piiri ja kontrollib, mis juhtub:
def rekursiivne (): rekursiivne () kui __nimi__ == '__main__': rekursiivne ()
Kui käivitate ülaltoodud koodi, saate käitamisaja erandi: RuntimeError: rekursiooni maksimaalne sügavus on ületatud. Python takistab teil funktsiooni loomist, mis jõuab lõpmatusse rekursiivsesse tsüklisse.
Rekursiooniga loendite tasandamine
Muid asju, mida saate teha rekursiooni abil, välja arvatud faktoorid, oletame, et soovite luua pesastatud loendist ühe, saate seda teha alloleva koodi abil:
def lamestama (a_list, flat_list = pole): kui flat_list pole ühtegi: flat_list = [] a_list-i üksuse jaoks: if isinstance (item, list): flatten (element, flat_list) muu: flat_list.append (item) tagastab flat_list, kui __name__ == '__main__': pesastatud = [1,2,3, [4,5], 6] x = lapik (pesastatud) print (x)
Väljund: [1,2,3,4,5,6]
Ülaltoodud koodi käivitamisel saadakse täisarvude loendi asemel üks loend, mis sisaldab sisendina täisarvude loendit. Sama saab teha ka muul viisil, Pythonis on midagi, mida nimetatakse itertools.chain () saate kontrollida funktsiooni ahela loomiseks kasutatud koodi (), see on teistsugune lähenemine sama asja tegemiseks nagu meie.
Rekursiooni eelised
Kood on rekursiivses funktsioonis puhas ja elegantne.
Liitühenduse saab rekursiooni abil jagada lihtsamateks alamprobleemideks.
Järjestuse genereerimine on rekursiooniga lihtsam kui mõne sisestatud iteratsiooni kasutamine.
Rekursiooni puudused
Rekursiivse funktsiooni taga oleva loogika järgimine võib mõnikord olla keeruline.
Rekursiivsed kõned on kallid (ebaefektiivsed), kuna need võtavad palju mälu ja aega.
Rekursiivseid funktsioone on raske siluda.
Selles artiklis nägime, mis on rekursioon ja kuidas saame probleemilausest arendada rekursiivseid funktsioone, kui matemaatiliselt saab probleemilauset defineerida. Lahendasime faktooriumi probleemi ja saime teada tingimused, mis on vajalikud faktoriaalide leidmiseks, kust suutsime need tingimused teisendada Pythoni koodiks, andes teile mõista, kuidas rekursioon töötab. Ma arvan, et on korralik, et Pythonil on sisseehitatud rekursioonilimiit, mis takistab arendajatel halvasti üles ehitatud rekursiivsete funktsioonide loomist. Oluline on märkida, et rekursiooni on raske siluda, kuna funktsioon kutsub ennast pidevalt.