Knyga/Rekursinės funkcijos

Ką išmoksi šiame skyriuje?

• Kas yra rekursija ir kodėl ji gali sukelti klaidą
• Kaip sukurti rekursinę funkciją su apsauga nuo begalinio kartojimosi
• Kaip veikia bazinė sąlyga (angl. base case)
• Kaip rekursija gali pakeisti ciklus
• Kaip su rekursija apskaičiuoti faktorialą, sandaugą, sumą
• Kaip generuoti Fibonačio seką
• Kaip pritaikyti rekursiją tekstų apdorojimui (pvz., apsukti žodį)

Vieniems šis skyrius gali pasirodyti naudingas, o kitiems - painus. Jeigu tau informacija pasirodys paini, tai nesuk galvos ir praleisk, prie šio skyriaus galėsi grįžti šiek tiek vėliau.

O dabar pabandom pasižiūrėti į klaidingai parašytą programą:

def manoFunkcija(): 
    print("labas")
    manoFunkcija() # ojojoi!

manoFunkcija()

Tokia programa keletą kartų parašys žodį labas ir tada nuluš... tai yra, galiausiai išspausdins kokią nors mįslingą klaidą, kaip RecursionError: maximum recursion depth exceeded. Kodėl?

Priežastis ta, kad manoFunkcija kiekvieną kartą kviečia save, tai yra, kviečia funkciją manoFunkcija. O tada manoFunkcija vėl kviečia save, tai yra manoFunkcija. Ir taip be galo!

Štai dar vienas panašus (irgi blogas) pavyzdys, pasižiūrėkim:

def pirmaFunkcija():
    print("pirma")
    antraFunkcija()

def antraFunkcija(): 
    print("antra")
    pirmaFunkcija() 

pirmaFunkcija()

Vėl nulūš programa, vėl bus išmesta klaida RecursionError. Priežastis ta pati: pirmaFunkcija visuomet kviečia funkciją antraFunkcija, o ši visuomet kviečia pirmaFunkcija. Ir taip be galo! Nei iš vienos funkcijos niekuomet nėra grįžtama.

Aš paprastai labai atsargiai žiūriu į funkcijas, kurios kviečia pačios save (tiesiogiai arba netiesiogiai), kaip kad pavyzdžiuose aukščiau.

Tačiau iš tiesų net ir tokias funkcijas įmanoma panaudoti, nesugriaunant programos. Tiesiog tokia funkcija turi kažkada nustoti kviesti save, ir tiesiog grįžti (return).

Štai nenulūžtančios programos pavyzdys:

def manoFunkcija(skaitiklis): 
    skaitiklis = skaitiklis + 1
    if skaitiklis > 3:
        return
    print("labas")
    manoFunkcija(skaitiklis) 

manoFunkcija(0)

Ši programa žodį "labas" išspausdins tik 3 kartus, ir tada baigsis. Jokios klaidos. Ar supratai, kodėl?

Parametras "skaitiklis" yra skirtas apsaugai nuo begalinio kartojimosi. Funkcija manoFunkcija kiekvieną kartą patikrina, ar skaitiklis neviršytas, ir kiekvieną kartą pasididina to skaitiklio reikšmę. Kai tik skaitiklis padidėjau daugiau, nei leidžiama, funkcija savęs nebekviečia - tiesiog grįžta.

Taigi, nors funkcija ir kviečia pati save, bet ne begalinį kartų skaičių.

Rekursija

Funkcijos, kurios kreipiasi pačios į save yra vadinamos rekursinėmis funkcijomis. Šio skyriaus pavyzdžiuose panagrinėsime tokias funkcijas. Tai palengvina programavimo užduočių sprendimų įgyvendinimą, nes kartais pakanka apsvarstyti tik vieną problemos žingsnį, o ne visą problemą iš karto. Be to tai leidžia išreikšti kai kurias matematines sąvokas paprastu, lengvai skaitomu kodu.

Bet kokią problemą, kurią galime išspręsti naudojant rekursiją, gali būti išspręsta naudojant ciklus. Jie veikia greičiau, bet kartais ciklus sunku atlikti teisingai.

Turbūt intuityviausias „rekursijos“ apibrėžimas yra toks:

 REKURSIJA
    Jei vis dar nesupranti, tai skaityk: REKURSIJA.

Pabandyk perskaityti dar kelis pavyzdžius.

Pavyzdžiai

atgalinis_skaičiavimas.py

def atgalinis_skaičiavimas(n):
    print(n)
    if n > 0:
        return atgalinis_skaičiavimas(n-1)

atgalinis_skaičiavimas(5)

Rezultatas:

5
4
3
2
1
0

Šis pavyzdys labai panašus į ankstesnįjį, tik skaitiklis ne didėja, o mažėja. Rekursinė funkcija atgalinis_skaičiavimas turi vidinę apsaugą nuo begalinio kartojimosi, tikrina kintamąjį n ir jį mažina, o nustoja save kvietinėti, kai n sumažėja iki nulio.

sudetingas_pavyzdys.py

def daug(a, b): # daug reiškia daugybą
    if b == 0:
        return 0
    lik = daug(a, b - 1) #lik reiškia likutį
    reikšmė = a + lik
    return reikšmė

rezultatas = daug(3, 2)
print("3 * 2 = ", rezultatas)

Iš esmės ši programa - tai teigiamų sveikųjų skaičių daugyba (iš tikrųjų Python'o programavimo kalboje daugybos funkcionalumas yra integruotas ir jo išradinėti nebūtina, tiesiog mes pabandėme suprogramuoti, kaip daugybą galima būtų pakeisti sudėties ir atimties veiksmais).

Kas nutinka, pirmą kartą iškvietus funkciją daug(3, 2)?

Parametras a gauna jam priskirtą reikšmę 3, o parametras b - jam priskirtą reikšmę 2.

Kas nutinka tada?

Vykdoma eilutė if b == 0:. Kadangi b reikšmė yra 2, todėl eilutė return 0 praleidžiama.

Kas vyksta toliau?

Vykdoma eilutė lik = daug(a, b - 1). Ši eilutė nustato lokalaus kintamojo lik reikšmę į daug(a, b - 1) reikšmę. a reikšmė yra 3, o b - 2, todėl funkcija kviečia funkciją daug(3, 1)

Taigi kokia yra daug(3, 1) reikšmė?

Turime iškviesti funkciją daug() su parametrais 3 ir 1.

Kas nutinka toliau?

Funkcijos viduje a reikšmė būtų 3, o b reikšmė – 1. Kadangi jie yra lokalūs kintamieji, todėl jie neturi įtakos ankstesnėms a ir b reikšmėms.

Kas įvyksta toliau?

Kadangi b turi reikšmę 1, if sąlygos rezultatas yra neigiamas, todėl vykdoma kita eilutė lik = daug(a, b - 1).

Ką daro ši eilutė?

Dabar kintamajam lik priskiriam funkcijos daug(3, 0) reikšmė.

Kokia ši reikšmė?

Norėdami tai išsiaiškinti, turime dar kartą paleisti funkciją. Šį kartą a reikšmė yra 3, o b – 0.

Kas vyksta toliau?

Pirmoji vykdytinos funkcijos eilutė yra if b == 0:. b reikšmė 0, todėl kita vykdoma eilutė yra return 0

Ką daro return 0 eilutė?

Ši eilutė grąžina funkcijos reikšmę lygią 0 į tą vietą, kur ji buvo iškviesta.

Kas iš to?

Dabar mes žinome, kad daug(3, 0) grąžina reikšmę 0. Dar žinome, ką daro eilutė lik = daug(a, b - 1), nes paleidžiame funkciją daug() su parametrais 3 ir 0. Baigiame vykdyti daug(3, 0) ir dabar vėl pradedame vykdyti daug(3, 1). Kintamajam lik priskiriama reikšmė yra 0.

Kurią eilutę kompiuteris skaito po to?

Toliau vykdoma eilutė reikšmė = a + lik. Žinome, kad a = 3 ir lik = 0 todėl dabar reikšmė = 3.

Kas nutinka toliau?

Vykdoma eilutė return reikšmė, kuri grąžina reikšmę 3. Šis skaičius atsiranda iš funkcijos daug (3, 1) vykdymo. Iškvietus return, grįžtame prie daug(3, 2).

Kur yra daug(3, 2)?

Mes turėjome kintamuosius a = 3 ir b = 2 ir nagrinėjome eilutę lik = daug(a, b - 1).

Kas įvyksta?

Kintamajam lik priskiriama reikšmė 3. Kita eilutė reikšmė = a + lik priskiria kintamajam reikšmė reikšmę 3 + 3 arba 6.

Kas įvyksta toliau?

Pradedama vykdyti kita eilutė, kuri grąžina 6 iš funkcijos. Tuomet grįžtame prie eilutės rezultatas = daug(3, 2), kur kintamajam rezultatas dabar priskiriama reikšmė 6

Kas nutinka toliau?

Paleidžiama kita eilutė po funkcijos print ("3 * 2 =", rezultatas).

Ką ji daro?

Ji spausdina 3 * 2 = ir rezultatas reikšmę, kuri yra 6. Visa išspausdinta eilutė yra 3 * 2 = 6.

Taigi, kas čia įvyko apskritai?

Iš esmės panaudojome du skirtingus faktus, kad apskaičiuotume dviejų skaičių kartotinį. Pirmas, kad bet koks skaičius padauginus iš nulio yra nulis (x * 0 = 0). Antras, kad skaičius padaugintas iš kito skaičiaus yra lygus pirmo skaičiaus ir pirmo bei vienetu mažesnio už antrąjį sandaugos sumai (x * y = x + x * (y - 1)). Taigi ir čia 3 * 2 pirmiausiai paverčiamas į 3 + 3 * 1. Tada 3 * 1 paverčiamas į 3 + 3 * 0. Tuomet mes žinome, kad bet kuris skaičius padaugintas iš nulio yra nulis, todėl 3 * 0 yra 0. Kai viskas surašoma vienoje eilutėje, gauname 3 + 3 + 0

Štai kaip viskas veikia:

daug(3, 2)
3 + daug(3, 1)
3 + 3 + daug(3, 0)
3 + 3 + 0
3 + 3
6

faktorialas.py

💡 Faktorialas yra vienas iš klasikinių rekursijos pavyzdžių, dažnai naudojamas programavimo mokymuose.

def faktorialas(n):
    if n == 0:
        return 1
    if n < 0:
        return "Klaida, neigiami skaičiai neturi faktorialo reikšmių!!"
    return n * faktorialas(n - 1)

print("2! =", faktorialas(2))
print("3! =", faktorialas(3))
print("4! =", faktorialas(4))
print("5! =", faktorialas(5))
print("-3! =", faktorialas(-3))

Rezultatas:

2! = 2
3! = 6
4! = 24
5! = 120
-3! = Klaida, neigiami skaičiai neturi faktorialo reikšmių!!

Pratimai

1. Parašyk programą, kuri paprašytų vartotojo įvesti skaičių ir laipsnį. Naudodamas rekursija, atspausdink skaičių pakelta duotuoju laipsniu. (Pvz: 2³=8)

Sprendimas
rezultatas = int() def keltiLaipsniu(skaičius, laipsnis): if laipsnis == 0: return 1 return skaičius * keltiLaipsniu(skaičius, laipsnis - 1) rezultatas = keltiLaipsniu(2, 3) print(rezultatas)

2. Parašyk programą, kuri prašo vartotojo įvesti skaičių ir grąžina sumą nuo 1 iki to skaičiaus. Pavyzdžiui, jei įvedamas skaičius 5, programa grąžina 5 + 4 + 3 + 2 + 1 = 15. Nepamiršk naudoti rekursijos.

Sprendimas
def suma_iki_vieno(skaičius, suma): if skaičius == 0: return suma else: return skaičius + suma_iki_vieno(skaičius - 1, suma) įvestas_skaičius = int(input("Įvesk skaičių: ")) rezultatas = suma_iki_vieno(įvestas_skaičius, 0) print ("Suma nuo 1 iki", įvestas_skaičius, ':', rezultatas)

3. Parašyk programą, kuri išveda Fibonačio seką iki įvesto skaičiaus n. Fibonačio seka - tai tokia sveikųjų skaičių seka, kur kiekvienas skaičius yra lygus prieš jį buvusių skaičių sumai. Pirmieji sekos skaičiai: 0 1 1 2 3 5 8 13 21 ir t.t.

Sprendimas
def fibonači(n): if n <= 1: return n else: return fibonači(n-1) + fibonači(n-2) įvestas_skaičius = int(input("Įvesk skaičių: ")) for i in range(įvestas_skaičius): print(fibonači(i))

4. Parašyk programą, kuri prašo vartotojo įvesti žodį ir grąžina tą žodį parašytą iš kitos pusės. Pvz “Labas” = “sabaL”. Šios užduoties sprendimui tau prireiks daugiau žinių apie sąrašus.

Sprendimas
def apversk(žodis): if len(žodis) == 0: return žodis else: return apversk(žodis[1:]) + žodis[0] įvestas_žodis = input("Įvesk žodį: ") print(apversk(įvestas_žodis))