Knyga/Rekursinės funkcijos - Versijų istorija

ArturasNik 13:04, 15 rugsėjo 2025

2025-09-15T13:04:46Z

← Ankstesnė versija		16:04, 15 rugsėjo 2025 versija
1 eilutė:		1 eilutė:
	{{navigation \|previous=Klasės \|next=Modulių naudojimas}}		{{navigation \|previous=Klasės \|next=Modulių naudojimas}}

			=== 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.		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.
31 eilutė:		40 eilutė:
	</syntaxhighlight>		</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.		Vėl nulūš programa, vėl bus išmesta 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.		Aš paprastai labai atsargiai žiūriu į funkcijas, kurios kviečia pačios save (tiesiogiai arba netiesiogiai), kaip kad pavyzdžiuose aukščiau.
52 eilutė:		61 eilutė:
	Ši programa žodį "labas" išspausdins tik 3 kartus, ir tada baigsis. Jokios klaidos. Ar supratai, kodėl?		Š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.		Parametras "skaitiklis" yra skirtas apsaugai nuo begalinio kartojimosi. Funkcija <code>manoFunkcija</code> kiekvieną kartą patikrina, 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čų~~.		Taigi, nors funkcija ir kviečia pati save, bet ne begalinį kartų skaičių.

	==== Rekursija ====		==== 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.		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.		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.
85 eilutė:		94 eilutė:
	0		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.		Šis pavyzdys labai panašus į ankstesnįjį, 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'''		'''sudetingas_pavyzdys.py'''
151 eilutė:		160 eilutė:

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

	<syntaxhighlight lang="python">		<syntaxhighlight lang="python">
	def faktorialas(n):		def faktorialas(n):

ArturasNik 13:12, 6 rugpjūčio 2025

2025-08-06T13:12:16Z

← Ankstesnė versija		16:12, 6 rugpjūčio 2025 versija
1 eilutė:		1 eilutė:
	{{navigation \|next=Modulių naudojimas}}		{{navigation \|previous=Klasės \|next=Modulių naudojimas}}

	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.		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.
265 eilutė:		265 eilutė:
	\|}		\|}

	{{navigation \|next=Modulių naudojimas}}		{{navigation \|previous=Klasės \|next=Modulių naudojimas}}
	[[Category:Knyga]]		[[Category:Knyga]]

ArturasNik: Naujas puslapis: {{navigation |next=Modulių naudojimas}} 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ų par...

2024-10-10T10:24:23Z

Naujas puslapis: {{navigation |next=Modulių naudojimas}} 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ų par...

Naujas puslapis

{{navigation |next=Modulių naudojimas}}

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 išveda Fibonačio seką iki įvesto skaičiaus <code>n</code>. 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.

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

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 [[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 |next=Modulių naudojimas}}
[[Category:Knyga]]