Python Vadovėlis/Rekursija

Rekursija

Programavime rekursine funkcija vadinama funkcija, kuri iškviečia pati save.

Įvadas į rekursiją

Iki šiol Python'o programoje matėme funkcijas, kurios iškviečia kitas funkcijas. Tačiau funkcija gali iškviesti ir pati save. Pažvelkime į paprastą pavyzdį.

# Mitchell Aikens programa
# Nėra autorinių teisių
# 2010

sk = 0

def main():
    skaitliukas(sk)

def skaitliukas(sk):
    print(sk)
    sk+= 1
    skaitliukas(sk)

main()

Jei šią programą paleistum VS Code kodo redaktoriuje, ji veiktų amžinai. Vienintelis būdas sustabdyti ciklą būtų nutraukti vykdymą paspaudžiant Ctrl + C klaviatūroje. Tai yra begalinės rekursijos pavyzdys.

Galima ginčytis, kad rekursija yra tik dar vienas būdas atlikti tą patį dalyką kaip ir naudojant ciklą. Kai kuriais atvejais tai yra visiškai teisinga. Tačiau yra ir kitų rekursijos naudojimo būdų, kurie yra labai tinkami, o while arba for ciklai gali būti ne pats geriausias variantas.

Rekursija gali būti valdoma, kaip ir ciklai. Pažvelk į rekursinio ciklo pavyzdį.

# Mitchell Aikens programa
# Nėra autorinių teisių
# 2010
def main():
    ciklosk= int(input("Kiek kartų norėtum paleisti ciklą?\n"))
    skaitliukas = 1
    recurr(ciklosk,skaitliukas)

def recurr(ciklosk,skaitliukas):
    if ciklosk> 0:
        print("Tai yra ciklo iteracija",skaitliukas)
        recurr(ciklosk- 1,skaitliukas + 1)
    else:
        print("Ciklas yra pabaigtas.")

main()

Programoje naudojami argumentai/parametrai rekursijų skaičiui valdyti. Tiesiog naudok tai, ką jau žinai apie funkcijas, ir sek programos eigą. Tai paprasta išsiaiškinti. Jei kyla problemų, grįžk į Pažangių funkcijų pavyzdys.

Praktiniai rekursijos pritaikymai

Dažnai rekursija yra studijuojama pažengusiu informatikos lygiu. Rekursija dažniausiai naudojama sprendžiant sudėtingas problemas, kurias galima suskirstyti į mažesnes, identiškas problemas. Norint išspręsti problemą, rekursija nebūtina. Problemos, kurias galima išspręsti naudojant rekursiją, greičiausiai gali būti išspręstos ir su ciklais. Be to, ciklas gali būti efektyvesnis nei rekursinė funkcija. Rekursinėms funkcijoms reikia daugiau atminties ir išteklių nei ciklams, todėl daugeliu atvejų jos yra mažiau efektyvios. Šis naudojimo reikalavimas kartais vadinamas overhead. Galbūt galvoji: „Na, kam nerimauti su rekursija. Aš tiesiog naudosiu ciklą. Aš jau žinau, kaip sudaryti ciklą, ir tai yra daug daugiau darbo.“ Ši mintis suprantama, bet ne visai ideali. Sprendžiant sudėtingas problemas, rekursinę funkciją kartais lengviau, greičiau ir paprasčiau sukurti bei programuoti.

Pagalvokite apie šias dvi „taisykles“:

• Jei galiu išspręsti problemą su ciklu, be rekursijos, funkcija tiesiog grąžina reikšmę.
• Jei negaliu išspręsti problemos su cilku, be rekursijos, funkcija sumažina problemą iki mažesnės analogiškos problemos ir iškviečia pati save.

Pabandyk pritaikyti rekursinę funkciją faktorialui apskaičiuoti. Jei nesi susipažinęs su faktoriais, skaityk: Faktorialas

Skaičiaus n faktorialas n, yra žymimas kaip n!.

Štai keletas pagrindinių faktorialo taisyklių:

Jei n = 0 tai n! = 1

Jei n > 0 tai n! = 1 x 2 x 3 x ... x n

Pavyzdžiui, pažiūrėk į skaičiaus 9 faktorialą.

9! = 1 x 2 x 3 x 4 x 5 x 6 x 7 x 8 x 9

Pažiūrėk į programą, kuri rekursijos metodu apskaičiuoja bet kurio vartotojo įvesto skaičiaus faktorialą.

def main():
    sk = int(input("Įvesk neneigiamą sveikąjį skaičių.\n"))
    fakt = faktorialas(sk)
    print("Skaičiaus ", sk, " faktorialas yra ", fakt)

def faktorialas(sk):
    if sk == 0:
        return  1
    else:
        return sk * faktorialas(sk - 1)

main()

Rekursija taip pat naudinga išplėstinėje temoje, vadinamoje generatoriais. Norint sugeneruoti serijas 1, 2, 1, 3, 1, 2, 1, 4, 1, 2... reikės šio kodo:

def beprotiškas(min_):
    yield min_
    g=beprotiškas(min_+1)
    while True:
        yield next(g)
        yield min_

i = beprotiškas(1)

norint gauti kitą elementą, iškiviestum next(i)