Šioje pamokoje mes pamatysime Rekursija su pavyzdžiais „Python“. Programavimo rekursija yra labai galinga technika, ji atliekama naudojant funkcijas, kurios vadina save, mato tai kaip tam tikrą kilpą, nes tas pats kodas bus kartojamas kelis kartus, kol bus pasiektas sprendimas.
Charakteristikos, kurias turi turėti rekursinė funkcijaBazinis dėklasTai leis mums nutraukti funkciją tam tikru momentu ir begaliniai skambučiai neįvyks.
Rekursinis atvejisTokiu atveju mes dar kartą iškviečiame funkciją, tačiau priartėsime prie sprendimo. Pavyzdžiuose atrodys geriau.
PastabaSvarbu aiškiai suprasti pagrindinį atvejį ir žinoti, kad rekursinis atvejis artėja prie jo ir neįeina į begalinių skambučių būseną, tai yra dažna klaida pradedant rekursiją.
Pereikime prie pavyzdžių, kurie bus paprasti ir trumpi, kad juos būtų galima gerai įsisavinti.
1 pavyzdys - Faktorinis
Šiame pavyzdyje mes padarysime Išspręskite skaičiaus faktorialąJei norite sužinoti, kas yra faktorius, apsilankykite šioje nuorodoje. Čia yra kodas, o žemiau paaiškinu rekursinę funkciją.
def faktorius (skaičius): jei (skaičius == 0 arba skaičius == 1): grąžinkite dar 1: grąžinkite skaičių * faktoriumą (skaičius-1), jei __vardas__ == "__main__": pabandykite: num = int (įvestis ("Iš Kokio skaičiaus norite sužinoti faktoriumi? ")) If (skaičius <0): print (" Skaičius turi būti didesnis arba lygus 0 ") else: print (" Faktorialas ", num," yra ", faktorius (numeris)), išskyrus: spausdinti („ Tikimasi skaičiaus ") Mūsų rekursinė funkcija turi pagrindinę raidę if ir rekursyviąją kitoje. Matote, kad pagrindinis atvejis grąžina 1 ir kad jis pasiekiamas, kai funkcijai perduotas parametras yra 0 arba 1, kai šis atvejis pasiekiamas, funkcija daugiau neskambina. Rekursyviniu atveju mes turime iškviesti funkciją sau, bet kaip galite pamatyti, kaip sumažinate parametrą 1 (mes priartėjame prie pagrindinio atvejo). Paskutinė kodo dalis, nepriklausanti funkcijai, yra atsakinga tik už tai, kad paprašytų vartotojo numerio ir patikrintų, ar skambinti funkcijai jis yra didesnis arba lygus 0, nes koeficientas su neigiamais skaičiais neveikia.
Jei skambinsime į funkciją skaičiumi 4, tai yra faktoriumi (4), turėsime šiuos skambučius:
Skambinti 1: faktoriumi (4) Skambinti 2: 4 * faktoriumi (3) Skambinti 3: 3 * faktoriumi (2) Skambinti 4: 2 * faktoriumi (1)Skambinant faktoriumi su 1, skambučių nebėra ir jis grąžins 1, tada ši funkcija grąžins rezultatų grąžinimą į funkciją, kurią aš vadinu, grąža būtų tokia:
faktoriumi (1) = 1 faktoriumi (2) = 2 * 1 faktoriumi (3) = 3 * 2 faktoriumi (4) = 4 * 6Ir mes jau turime savo rezultatą, kuris yra 24, padauginus skaičius: 1 * 2 * 3 * 4. Toliau palieku ekrano kopiją, kai prašau koeficiento 5, kuris yra ne kas kita, kaip 5 padauginus iš koeficiento 4 (kurį mes jau žinome, kad yra 24) ir gauname 120. Taip pat galite pamatyti, kad jei vartotojas įterpia numerį negerai, tai:
2 pavyzdys - Sudėjimas / atimtis
Šiame pavyzdyje aš įtraukiau rekursinę funkciją, kad pridėčiau ar atimčiau, žinoma, šis pavyzdys paprastai nepasitaiko realiame gyvenime, tačiau kaip pavyzdys jis veikia:
def veikti (skaičius1, skaičius2): jei (skaičius2 == 0): grąžinkite skaičių1 elifas (skaičius2 <0): grįžkite veikti (skaičius1-1, skaičius2 + 1) kitaip: grįžkite veikti (skaičius1 + 1, skaičius2-1), jei __vardas__ == "__main__": print ("10 ir 3 pridėjimas:", operacija (10, 3)) print ("Pridedama 5 ir -2:", veikia (5, -2)) Čia mes turime pagrindinį atvejį ir 2 rekursyvius atvejus, kad žinotume, kokiu būdu paliesti, nes priklausomai nuo to, ar skaičius yra teigiamas, ar neigiamas, turėsime elgtis kitaip. Veikimo funkcija gauna 2 skaičius, o algoritmas pasirūpins, kad jis atimtų arba pridėtų skaičių 2 ir perduotų jį skaičiui 1 (jei skaičius 2 yra teigiamas, aš atimsiu 1 iš skaičiaus 2 ir pridėsiu jį prie skaičiaus 1), taigi, kol kintamasis skaičius2 bus lygus iki 0.
Pavyzdžiui, matydami skambučius pridėsime 3 + 2.
1 skambutis: valdyti (3,2) 2 skambutis: valdyti (4,1) 3 skambutis: valdyti (5,0)Šiuo atveju, kai mes pradedame veikti (5,0), nieko daugiau neturime padaryti, mes gauname rezultatą tiesiogiai (kitaip nei faktoriaus atveju, kuris turėjo atlikti dauginimą). Štai kodo vykdymo rezultatas:
PastabaNors su rekursija turime elegantišką sprendimą ir paprastai trumpesnį, jis turėtų būti naudojamas, kai neturime kitos išeities, tačiau jei mes galime pasinaudoti iteraciniu variantu, tai bus geresnis pasirinkimas, nes jis sunaudoja mažiau atminties ir paprastai yra greitesnis.
Ar jums patiko ir padėjo ši pamoka?Galite apdovanoti autorių paspausdami šį mygtuką, kad suteiktumėte jam teigiamą tašką
