Piper pitéje

Rekurzió

Egy függvény akkor rekurzív, ha önmagát hívja.

A függvényhívás és a ciklus között az egyik lényeges különbség az, hogy függvényhíváskor a visszatérési cím a verembe kerül. Ez azt jelenti, hogy egy rekurzív függvény általában több veremtárhelyet igényel, mint egy vele egyenértékű ciklus.

Következésképpen előfordulhat, hogy egy függvény, amely folyton önmagát hívja, végül kimeríti a teljes veremtárhelyet. Ezt veremtúlcsordulásnak nevezik.

Ezért minden rekurzív függvénynek legalább egy alapesettel kell rendelkeznie, ami olyan helyzet, amikor a függvény önmaga meghívása nélkül tér vissza. Minden rekurzív hívásnak előbb-utóbb el kell jutnia egy alapesethez.

Például a n! = n * (n - 1) * ... * 1 faktoriálisfüggvény rekurzívan definiálható úgy, hogy az alapeset 1:

factorial:
    ; the argument `n` is passed on `rdi`
    ; the factorial will be returned on `rax`

    cmp rdi, 1
    jle .base_case     ; base case -> if rdi <= 1, return 1

    push rdi           ; save n
    dec rdi            ; rdi = n - 1
    call factorial     ; recursive call, rax = (n - 1)!
    pop rdi            ; restore n
    imul rax, rdi      ; rax = n * (n - 1)! = n!
    ret
.base_case:
    mov rax, 1
    ret

Vegyük észre, hogy a factorial rekurzív hívás előtt elvégzi a push rdi, utána pedig a pop rdi műveletet. Ez azért van, mert a rekurzív hívás visszatérése után még szüksége van n-re az n * (n-1)! kiszámításához.

Az is figyelmet érdemel, hogy a callee-saved regiszterek használata sem oldaná meg ezt a problémát.

Bár egy rekurzív függvény önmaga lehetséges hívója, ő maga is hívottja egy másik függvénynek. Ez azt jelenti, hogy a függvénynek a használatuk előtt meg is kell őriznie a callee-saved regisztereket, használatuk után pedig vissza kell állítania az értéküket. Erre általában egy push/pop sorozatot használunk, ahogyan azt egy korábbi fogalomnál is láttuk.

Mivel a rekurzív függvény minden kerete, az alapeset kivételével, maga is hívó, amelynek meg kell őriznie a saját lokális változóit, ezt a push/pop sorozatot minden keretnél meg kell ismételni. Még ha a változót regiszterek használata nélkül, közvetlenül a verembe tárolnánk is, az is ugyanannyiba, keretenként 8 bájtba kerülne.

Ez azt jelenti, hogy minden rekurzív hívás 8 bájttal növeli a vermet a call által verembe tett visszatérési cím miatt, plusz további 8 bájttal minden lokális változó után, amelyet meg kell őriznie. A függvény minden keretnél tovább növeli ezekkel a bájtokkal a vermet, amíg el nem éri az alapesetét. Csak ekkor kezd el lebontani fordított sorrendben, minden rekurzív hívás annyi pop-ot hajt végre, amennyire szüksége van, majd egy ret-et.

Például ha a factorial függvényt 10 argumentummal hívnánk meg, kilencszer hívná meg önmagát, mielőtt elérné az 1 alapesetet. Ekkor már 144 bájtot használtunk volna fel az n (8 bájt) és a visszatérési cím (8 bájt) tárolására minden korábbi keretnél.

Farokhívás

Bizonyos helyzetekben a függvény egy másik függvény meghívása után, a visszatérés előtt már nem végez semmilyen további munkát.

Vegyük például a következőt:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    call times_three
    ret

A triple_of_square függvény:

• megszorozza a kapott argumentumot (az rdi-ben) önmagával, megkapva annak négyzetét;
• majd meghívja a times_three függvényt, amely a kapott argumentum háromszorosával tér vissza.

Ennek eredményeként a triple_of_square a 3*x² értékkel tér vissza, ahol x a függvény argumentuma, amelyet az rdi-ben adunk át.

Vegyük észre, hogy a triple_of_square a times_three meghívása után már nem végez semmilyen munkát, a függvény egyszerűen visszatér. Egy ilyen helyzetben a függvény a call helyett használhat jmp-et, és átadhatja a vezérlést a meghívott függvénynek:

times_three:
    imul rax, rdi, 3
    ret

triple_of_square:
    imul rdi, rdi
    jmp times_three

Ezt nevezik farokhívásnak.

A farokhívás fő előnye, hogy elkerüli a call többletköltségét. A call egy visszatérési címet tesz a verembe, és ahhoz, hogy a vezérlés visszatérjen arra a pontra, lennie kell egy hozzá illő ret-nek.

A farokhívás mindkettőt kihagyja: nincs visszatérési cím, amit a verembe kellene tenni, és nincs plusz ret, amivel párosulnia kellene, csak a meghívott függvény saját ret-je.

Farokrekurzió

A farokhívás különösen hasznos az olyan rekurzív függvényeknél, amelyek visszatérés előtt sokszor meghívhatják önmagukat.

Azonban nem minden rekurzív hívás alakítható át közvetlenül farokhívássá. Mivel a jmp átadja a vezérlést a meghívott függvénynek, a hívó a farokhívás után már nem végezhet további munkát.

Például a korábbi factorial függvény nem farokrekurzív. A rekurzív hívás után még meg kell szoroznia az eredményt az aktuális n-nel az imul rax, rdi utasítással.

Ilyen helyzetekben néha lehetőség van egy akkumulátor használatára, amely összegyűjti a részszámításokat, és amelyet a végén visszaadunk. Például definiálhatunk egy factorial_helper függvényt, amely elvégzi a munka nagy részét, majd a factorial beállít egy akkumulátort, és átadja a vezérlést a factorial_helper-nek:

factorial_helper:
    ; the argument `n` is passed on `rdi`
    ; `rax` is used as an accumulator and will be returned at the end

    cmp rdi, 1
    jle .base_case

    imul rax, rdi        ; we accumulate the partial result on `rax`
    dec rdi              ; rdi = n - 1
    jmp factorial_helper ; tail call to accumulate (n - 1)!
.base_case:
    ret                  ; returns the factorial already accumulated on `rax`

factorial:
    mov rax, 1           ; initial value for the accumulator
    jmp factorial_helper ; tail call

Mivel a rekurzív hívás után már nem történik több munka, rdi-t sem kell többé megőriznünk. Nincs call vagy push rdi, így minden rekurzív iteráció 0 bájttal növeli a vermet: nem használunk további veremtárhelyet. Ez a változat tetszőlegesen nagy n-nel is elboldogul anélkül, hogy túlcsordulna a verem. Egyszerre hatékonyabb és biztonságosabb.

Bizonyos esetekben a függvények sorrendjének átalakításával még a segédfüggvényre mutató jmp is elkerülhető. Például a factorial és a triple_of_square így írható át:

factorial:
    mov rax, 1
factorial_helper:
    cmp rdi, 1
    jle .base_case

    imul rax, rdi
    dec rdi
    jmp factorial_helper
.base_case:
    ret

triple_of_square:
    imul rdi, rdi
times_three:
    imul rax, rdi, 3
    ret

A fenti kódrészletben a factorial végrehajtása átfolyik a factorial_helper-be. Ugyanez történik a triple_of_square és a times_three esetében is. Mindkét esetben a végrehajtás sorban folytatódik, és úgy tűnik, mintha a farokfüggvény csak egy helyi címke lenne a „fő” függvényen belül.

A valóságban lényegében nincs különbség egy helyi címke és egy függvény között. Az x86-64 assembly nem kezeli különlegesen egyiket sem, ezek csupán címek egy végrehajtható kódot tartalmazó szakaszban, például a section .text-ben.

Így egy farokrekurzív függvény lényegében ugyanannak tekinthető, mint egy ciklus, amelyben a rekurzív hívás visszaugrik a tetejére, az alapeset pedig az a feltétel, amely befejezi a ciklust.