Rekurzió ebben a kurzusban:

A(z) Rekurzió fogalomról

A rekurzió arra való, hogy egy függvényen belül ismételten végrehajtsunk kódot úgy, hogy a függvény önmagát hívja. Az önmagukat hívó függvényeket rekurzív függvényeknek nevezzük. A rekurzió a ciklus, illetve az iteráció egy másik megvalósítási módjaként is felfogható. És ahogy a ciklusoknál, itt is egy Boolean-kifejezés vagy egy True/False vizsgálat dönti el, mikor álljon le a rekurzív végrehajtás.

A ciklusoktól eltérően a leállás nélküli rekurzió Pythonban nem futhat a végtelenségig. Az egyes függvényhívásokban használt értékek a Python-értelmező vermének saját keretébe kerülnek. Ha a függvényhívások összes száma több helyet foglal el, mint amennyi a veremben rendelkezésre áll, az hibát eredményez.

Ciklusos és rekurzív megvalósítás

A ciklus és a rekurzió hasonlónak tűnhet, hiszen mindkettő iteratív. Ugyanakkor másképp néznek ki, mind a kód, mind a megvalósítás szintjén. A ciklus ugyanabban a keretben zajlódhat le a hívási veremben. Ezt általában úgy oldják meg, hogy egy vagy több változó értékét frissítik, és így minden iterációhoz fokozatosan fenntartják az állapotot. Ez hatékony megvalósítás, de a kód első ránézésre kissé zsúfolt lehet.

A rekurzió a változóállapot frissítése helyett közvetlenül frissített értékeket adhat át argumentumként ugyanazon függvény következő hívásának (iterációjának). Ez letisztázza a függvény törzsét, és világosabbá teheti, hogyan történik az egyes frissítések. Ugyanakkor kevésbé hatékony megvalósítás is, mert ugyanazon függvény minden hívása újabb keretet ad a veremhez.

Rekurzió: miért és miért nem?

Ha fennáll a veremhiba vagy a veremtúlcsordulás kockázata, miért használna bárki rekurzív stratégiát egy probléma megoldására? Olvashatóság, nyomon követhetőség és szándék. Előfordulhatnak olyan helyzetek, amikor egy megoldás olvashatóbb és/vagy könnyebben végiggondolható rekurzióval kifejezve, mint ciklussal. A programnak lehetnek olyan megkötései is, amelyek az adatok használatához/módosításához, a bonyolultság kezeléséhez, a felelősség átruházásához vagy a munkaterhelés megszervezéséhez kapcsolódnak.

A rekurzióra jól ráillő problémák közé tartoznak az összetett, de ismétlődő problémák, amelyek idővel egyre kisebbek lesznek, különösen az oszd meg és uralkodj algoritmusok és a kumulatív algoritmusok. Mivel azonban a Python korlátozza, hány keret lehet a veremben, nem minden probléma jár jól egy teljesen rekurzív stratégiával. A rekurzióra kevésbé természetesen illő problémák közé tartoznak azok, amelyek állandó állapotban vannak, de meghatározott számú cikluson keresztül ismétlődniük kell, az aszinkron végrehajtást igénylő problémák, valamint azok a helyzetek, amelyek nagyon sok iterációt kívánnak.

Ciklusos és rekurzív stratégia: Indira bizonytalansága

Indira havi társadalombiztosítási ellátását minden hónap második szerdáján automatikusan a bankszámlájára utalják. Indira aggódik, hogy rendben tudja-e vezetni a csekkfüzetét. Fél, hogy csekket ír, mielőtt a pénze megérkezik. Megkéri az unokáját, Adyát, hogy adjon neki egy listát azokról a dátumokról, amikor a pénze megjelenik a számláján.

Adya, aki épp most tanul Pythonban programozni, megír egy programot az első gondolatai alapján. Szeretne visszaadni egy list-et a befizetési dátumokból, hogy ki lehessen nyomtatni őket. Olyan függvényt szeretne írni, amely bármelyik évre működik. Arra az esetre, ha a menetrend megváltozik (vagy ha más rokonok is szeretnék, hogy Adya kiszámolja a befizetési menetrendjüket), úgy dönt, hogy a függvénynek külön paramétert kell kapnia a hét napjára. Végül Adya úgy dönt, hogy a függvénynek paraméterre van szüksége arra is, hogy a hónap hányadik adott napjáról van szó: az első, a második stb. Mindezek figyelembevételével úgy dönt, hogy a datetime modulból importált date osztályt használja. Mindezt összerakva Adya ezt írja:

from datetime import date


def paydates_for_year(year, weekday, ordinal):
    """Returns a list of the matching weekday dates.
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    output = []

    for month in range(1, 13):
        for day_num in range(1, 8):
            if date(year, month, day_num).isoweekday() == weekday:
                output.append(date(year, month, day_num + (ordinal - 1) * 7))
                break
    return output

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year(2022, 3, 2))

Ez az első iteráció működik, de Adya azon tűnődik, hogy át tudná-e írni a kódot kevesebb sorral és kevesebb egymásba ágyazott ciklussal. Azt is olvasta, hogy jó minimalizálni az állapot módosítását, ezért szeretné megnézni, el tudja-e kerülni néhány változója, például az output, a month és a day_num módosítását.

A rekurzióról is tud, és elgondolkodik, hogyan alakíthatná át a programját rekurzív megközelítésre. A ciklusos függvényében létrehozott és módosított változókat argumentumként is átadhatná. Ahelyett, hogy a függvényén belül módosítaná a változókat, frissített értékeket adhatna át argumentumként a következő függvényhívásnak. Ezzel a szándékkal jut el ehhez a rekurzív megoldáshoz:

from datetime import date


def paydates_for_year_rec(year, weekday, ordinal, month, day_num, output):
    """Returns a list of the matching weekday dates
    
    Arguments:
        year (int): The year (e.g. 2022).
        weekday (int): The weekday number (e.g. 3 for Wednesday).
        ordinal (int): Which weekday of the month (e.g. 2 for the second day).
        month (int): The month number currently being processed.
        day_num (int): The day number of the month currently being processed.
    
    Returns:
        output (list): Matching weekday dates.
    """
    
    if month == 13:
        return output
        
    if date(year, month, day_num).isoweekday() == weekday:
        return paydates_for_year_rec(
                 year, weekday, ordinal, month + 1, 1, output
                 + [date(year, month, day_num + (ordinal - 1) * 7)]
                 )
    
    return paydates_for_year_rec(year, weekday, ordinal, month, day_num + 1, output)

# find the second Wednesday of the month for all the months in 2022
print(paydates_for_year_rec(2022, 3, 2, 1, 1, []))

Adya örül, hogy nincsenek többé egymásba ágyazott ciklusok, nincs módosított állapot, és két sorral kevesebb a kód!

Kicsit aggasztja, hogy a rekurzív megközelítés több lépést használ, mint a ciklusos, így kevésbé „hatékony”. De a probléma rekurzióval való újraírása biztosan segített neki kezelni a csúnya egymásba ágyazott ciklusokat (a teljesítmény kockázatát), a kiterjedt állapotmódosítást és a bonyolult feltételes logika körüli zavart. Ráadásul „olvashatóbbnak” is érzi, és biztos benne, hogy amikor egy szünet után visszatér ehhez a kódhoz, könnyebben átolvassa és felidézi, mit csinál.

A jövőben Adya talán először rekurzívan próbálja majd megoldani a problémákat. Lehet, hogy könnyebb lesz neki először világos lépésekben végigjárni a problémát, amikor az egymásba ágyazás, a módosítás és a bonyolultság minimális. Miután kitalálta az alapvető logikát, arra összpontosíthat, hogy a kezdeti rekurzív lépéseit egy hatékonyabb ciklusos megközelítéssé optimalizálja.

Később, amikor megismerkedik a tuples fogalommal, Adya további „optimalizálási” lehetőségeket is fontolóra vehet, például egy list comprehension használatát a Calendar.itermonthdates metódussal, vagy bizonyos értékek memorizálását.

Rekurzív változat: a farokhívás

Farokhívásról akkor beszélünk, amikor egy függvény utolsó utasítása csak önmagát hívja, semmi mást. Ez a példa nem farokhívás, mert a függvény 1-et ad hozzá az önmaga hívásából kapott eredményhez:

def print_increment(step, max_value):
    if step > max_value:
        return 1
    print(f'The step is {step}')
    return 1 + print_increment(step + 1, max_value)


def main():
    retval = print_increment(1, 2)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

Ez a következőt írja ki:

The step is 1
The step is 2
retval is 3 after recursion

Ahhoz, hogy farokhívássá alakítsd, tedd a retval-t a print_increment paraméterévé.

def print_increment(step, max_value, retval):
    if step > max_value:
        return retval
    print(f'The step is {step}')
    return print_increment(step + 1, max_value, retval + 1)


def main():
    retval = print_increment(1, 2, 1)
    print(f'retval is {retval} after recursion')

if __name__ == "__main__":
    main()

Lehet, hogy a farokhívást még könnyebb végiggondolni, mint egy nem farokhívás rekurzív hívást. Rekurzió használatakor azonban mindig fontos tudni, hogy nem lesz annyi iteráció, hogy a verem túlcsorduljon.

Rekurziós korlátok Pythonban

Egyes nyelvek optimalizálni tudják a farokhívásokat, így minden rekurzív hívás a függvény első hívásának veremkeretét használja újra (hasonlóan ahhoz, ahogy egy ciklus újrahasznál egy keretet), ahelyett hogy újabb keretet adna a veremhez. A Python nem tartozik ezek közé a nyelvek közé. A veremtúlcsordulás ellen a Python egy rekurziós korláttal védekezik, amely alapértelmezésben ezer keret. Amikor az értelmező észleli, hogy a rekurziós korlátot túllépték, RecursionError kivételt dob. A sys.setrecursionlimit metódussal meg lehet növelni a rekurziós korlátot, de ezzel kockáztatod, hogy futásidőben szegmentálási hiba keletkezik, ami összeomlasztja a programot, és esetleg az operációs rendszert is.

További források

Ha többet szeretnél megtudni a rekurzió Pythonban való használatáról, kezdd ezekkel:

• python-programming: recursion
• Real Python: python-recursion
• Real Python: python-thinking-recursively