Vadovėlis/Rekursinės funkcijos

2023-02-10T09:45:54Z

Mantas:

{{navigation |previous=Funkcijų apibrėžimas |next=Sąrašai}}

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ą:

<syntaxhighlight lang="python">
def manoFunkcija():
print("labas")
manoFunkcija() # ojojoi!

manoFunkcija()
</syntaxhighlight>

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

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

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

<syntaxhighlight lang="python">
def pirmaFunkcija():
print("pirma")
antraFunkcija()

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

pirmaFunkcija()
</syntaxhighlight>

Vėl nulūš programa, vėl nutiks klaida <code>RecursionError</code>. Priežastis ta pati: <code>pirmaFunkcija</code> visuomet kviečia funkciją <code>antraFunkcija</code>, o ši visuomet kviečia <code>pirmaFunkcija</code>. 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 (<code>return</code>).

Štai nenulūžtančios programos pavyzdys:

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

manoFunkcija(0)
</syntaxhighlight>

Š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 <code>manoFunkcija</code> kiekvieną kartą stropiai pasitikslina, ar <code>skaitiklis</code> 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čų.

==== 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ų spendimų į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'''
<syntaxhighlight lang="python">
def atgalinis_skaičiavimas(n):
print(n)
if n > 0:
return atgalinis_skaičiavimas(n-1)

atgalinis_skaičiavimas(5)
</syntaxhighlight>

Rezultatas:
5
4
3
2
1
0

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

'''sudetingas_pavyzdys.py'''
<syntaxhighlight lang="python">
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)
</syntaxhighlight>

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 <code>a</code> gauna jam priskirtą reikšmę 3, o parametras <code>b</code> - jam priskirtą reikšmę 2.
; Kas nutinka tada?
: Vykdoma eilutė <code>if b == 0:</code>. Kadangi <code>b</code> reikšmė yra 2, todėl eilutė <code>return 0</code> praleidžiama.
; Kas vyksta toliau?
: Vykdoma eilutė <code>lik = daug(a, b - 1)</code>. Ši eilutė nustato lokalaus kintamojo <code>lik</code> reikšmę į <code>daug(a, b - 1)</code> reikšmę. <code>a</code> reikšmė yra 3, o <code>b</code> - 2, todėl funkcija kviečia funkciją <code>daug(3, 1)</code>
; Taigi kokia yra <code>daug(3, 1)</code> reikšmė?
: Turime iškviesti funkciją <code>daug()</code> su parametrais 3 ir 1.
; Kas nutinka toliau?
: Funkcijos viduje <code>a</code> reikšmė būtų 3, o <code>b</code> reikšmė – 1. Kadangi jie yra lokalūs kintamieji, todėl jie neturi įtakos ankstesnėms <code>a</code> ir <code>b</code> reikšmėms.
; Kas įvyksta toliau?
: Kadangi <code>b</code> turi reikšmę 1, if sąlygos rezultatas yra neigiamas, todėl vykdoma kita eilutė <code>lik = daug(a, b - 1)</code>.
; Ką daro ši eilutė?
: Dabar kintamajam <code>lik</code> priskiriam funkcijos <code>daug(3, 0)</code> reikšmė.
; Kokia ši reikšmė?
: Norėdami tai išsiaiškinti, turime dar kartą paleisti funkciją. Šį kartą <code>a</code> reikšmė yra 3, o <code>b</code> – 0.
; Kas vyksta toliau?
: Pirmoji vykdytinos funkcijos eilutė yra <code>if b == 0:</code>. <code>b</code> reikšmė 0, todėl kita vykdoma eilutė yra <code>return 0</code>
; Ką daro <code>return 0</code> eilutė?
: Ši eilutė grąžina funkcijos reikšmę lygią 0 į tą vietą, kur ji buvo iškviesta.
; Kas iš to?
: Dabar mes žinome, kad <code>daug(3, 0)</code> grąžina reikšmę 0. Dar žinome, ką daro eilutė <code>lik = daug(a, b - 1)</code>, nes paleidžiame funkciją <code>daug()</code> su parametrais 3 ir 0. Baigiame vykdyti <code>daug(3, 0)</code> ir dabar vėl pradedame vykdyti <code>daug(3, 1)</code>. Kintamajam <code>lik</code> priskiriama reikšmė yra 0.
; Kurią eilutę kompiuteris skaito po to?
: Toliau vykdoma eilutė <code>reikšmė = a + lik</code>. Žinome, kad <code>a = 3</code> ir <code>lik = 0</code> todėl dabar <code>reikšmė = 3</code>.
; Kas nutinka toliau?
: Vykdoma eilutė <code>return reikšmė</code>, kuri grąžina reikšmę 3. Šis skaičius atsiranda iš funkcijos <code>daug (3, 1)</code> vykdymo. Iškvietus <code>return</code>, grįžtame prie <code>daug(3, 2)</code>.
; Kur yra <code>daug(3, 2)</code>?
: Mes turėjome kintamuosius <code>a = 3</code> ir <code>b = 2</code> ir nagrinėjome eilutę <code>lik = daug(a, b - 1)</code>.
; Kas įvyksta?
: Kintamajam <code>lik</code> priskiriama reikšmė 3. Kita eilutė <code>reikšmė = a + lik</code> priskiria kintamajam <code>reikšmė</code> reikšmę <code>3 + 3</code> arba 6.
; Kas įvyksta toliau?
: Pradedama vykdyti kita eilutė, kuri grąžina 6 iš funkcijos. Tuomet grįžtame prie eilutės <code>rezultatas = daug(3, 2)</code>, kur kintamajam <code>rezultatas</code> dabar priskiriama reikšmė 6
; Kas nutinka toliau?
: Paleidžiama kita eilutė po funkcijos <code>print ("3 * 2 =", rezultatas)</code>.
; Ką ji daro?
: Ji spausdina <code>3 * 2 =</code> ir <code>rezultatas</code> reikšmę, kuri yra 6. Visa išspausdinta eilutė yra <code>3 * 2 = 6</code>.
; 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 <code>(x * 0 = 0)</code>. 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 <code>(x * y = x + x * (y - 1))</code>. Taigi ir čia <code>3 * 2</code> pirmiausiai paverčiamas į <code>3 + 3 * 1</code>. Tada <code>3 * 1</code> paverčiamas į <code>3 + 3 * 0</code>. Tuomet mes žinome, kad bet kuris skaičius padaugintas iš nulio yra nulis, todėl <code>3 * 0</code> yra 0. Kai viskas surašoma vienoje eilutėje, gauname <code>3 + 3 + 0 </code>

Štai kaip viskas veikia:

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

'''faktorialas.py'''
<syntaxhighlight lang="python">
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))
</syntaxhighlight>

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<sup>3</sup>=8)

{| class="mw-collapsible mw-collapsed wikitable"
! colspan=2 | Sprendimas  
|-
|
<syntaxhighlight lang="python">
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)
</syntaxhighlight>
|-
|}

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.

{| class="mw-collapsible mw-collapsed wikitable"
! colspan=2 | Sprendimas  
|-
|
<syntaxhighlight lang="python">
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)
</syntaxhighlight>
|-
|}

3. 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 [[Vadovėlis/Daugiau apie sąrašus|daugiau žinių apie sąrašus]].

{| class="mw-collapsible mw-collapsed wikitable"
! colspan=2 | Sprendimas  
|-
|
<syntaxhighlight lang="python">
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))
</syntaxhighlight>
|-
|}

{{navigation |previous=Funkcijų apibrėžimas |next=Sąrašai}}

Pitonas - Naudotojo indėlis [lt]

Vadovėlis/Rekursinės funkcijos