Python Vadovėlis/Rekursinės funkcijos

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 į mūsų parašytą programą:

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 teigiama sveikųjų skaičių daugybos funkcija (reikia atkreipti dėmesį į tai, kad Python'o programavimo kalboje jau yra integruota funkcija dauginimui, čia mes patys parašėme lengvai suprantamą pavyzdį (jeigu kurtume tokią funkciją patys), kuris parodo kaip atrodo daugybos veiksmas. Šioje programoje gali pamatyti rekursijos naudojimą, tai yra iteracijos (kartojimo) forma, kai funkcija yra pakartotinai iškviečiama, kol bus įvykdyta sukurta išvesties sąlyga. Programa naudoja pakartotinius papildymus, kad gautų tą patį rezultatą kaip ir daugyba: pavyzdžiui 3 + 3 (sudėtis) duoda tą patį rezultatą kaip ir 3 * 2 (daugyba).

Klausimas: Ką pirmiausia daro programa?

Atsakymas: Pirmiausia yra aprašyta daugybos funkcija:

def daug(a, b):
    if b == 0:
        return 0
    lik = daug(a, b - 1)
    reikšmė = a + lik 
    return reikšmė

Ši funkcija paima du parametrus ir grąžina reikšmę. Vėliau šią funkciją galima bus iškviesti.

Kas nutinka toliau?

Vykdoma kita eilutė einanti po funkcijos rezultatas = daug(3, 2)

Ką daro ši eilutė?

Ši eilutė priskiria funkcijos daug(3, 2) grąžinamą reikšmę kintamajam rezultatas.

Ką grąžina daug(3, 2)?

Norėdami tai išsiaiškinti, turime peržiūrėti funkciją daug().

Kas vyksta su kodu?

Kintamasis a gauna jam priskirtą reikšmę 3, o kintamasis 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 paleisti funkciją daug() su parametrais, kurie yra 3 ir 1.

Kas nutinka toliau?

Lokalūs kintamieji vėl pasileidus kodui jau yra nustatyti, todėl 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

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

faktorialas.py

#apibrėžia funkciją, kuri apskaičiuoja koeficientą

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ų!!

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

Pratimai

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)