8.4 Rekurzív függvények assemblyben

8.4.1 Miért igényel külön figyelmet a rekurzió?

Egy fa bejárása vagy egy rekurzív feldolgozó assembly-átiratakor nem elég a matematikai algoritmust követni: minden aktív hívásnak meg kell őriznie a saját folytatásához szükséges állapotot. A hibás regisztermentés rossz eredményhez, a hiányzó megállási feltétel pedig a verem kimerüléséhez vezethet.

A rekurzív függvény (recursive function) közvetlenül vagy más függvényeken keresztül önmagát hívja. Egy aktiváció (activation) a függvény egy konkrét, még be nem fejezett végrehajtása. Az aktivációk ugyanazt az utasítássorozatot használják, de külön megőrzött állapotra van szükségük.

Ebben az alfejezetben az ARMv8-A alapprofil A64 ISA-ját, little-endian Linux-környezetet és az AAPCS64 szerződését használjuk. Előfeltétel a Prológus és epilógus: regisztermentés és keretkezelés ismerete. A példában minden aktiváció azonos méretű keretet foglal; dinamikus méretű lokális objektumokat nem használunk.

8.4.2 Rekurzió mint egymásba ágyazott keretek láncolata

A nemnegatív egész argumentumú faktoriális definíciója:

$f(n)= \begin{cases} 1, & n\leq 1,\\ n\cdot f(n-1), & n>1. \end{cases}$

Itt $n$ dimenzió nélküli, előjel nélküli egész. A $n\leq1$ feltétel a báziseset (base case): ez az ág további hívás nélkül állítja elő az eredményt.

Az A64 megvalósításban az argumentum és az eredmény az X0 regiszterben halad. Az önhívás azonban felülírhatja az X0 tartalmát, ezért az aktuális $n$ értéket máshol kell megőrizni a visszatérés utáni szorzáshoz.

Az A64 X19 erre alkalmas, mert az AAPCS64 szerint megőrzendő regiszter. Ez nem jelent automatikus hardveres védelmet: minden aktivációnak el kell mentenie a belépési X19 értéket, majd vissza kell állítania azt.

Ugyanígy minden további hívást végrehajtó aktivációnak meg kell őriznie a saját visszatérési címét. Az A64 BL az X30 regiszterbe írja a folytatás címét, így az újabb önhívás felülírná az előző címet.

A folyamat két szakasza:

Lefelé haladás: prológus, bázisvizsgálat, újabb hívás.
Visszafejtés: részeredmény felhasználása, epilógus, visszatérés.

A rekurzióhoz nincs külön „rekurzív utasítás”: közönséges függvényhívások láncolatáról van szó.

8.4.3 Kidolgozott példa: 64 bites faktoriális

Munkakönyvtár: ~/arm-labor/a64/a030/ — az alfejezet minden laborfájlja ide kerül, és minden parancs innen futtatandó (a könyvtárrendet a Labor-alapkörnyezet alfejezet írja le).

mkdir -p ~/arm-labor/a64/a030
cd ~/arm-labor/a64/a030

Az interfész pontos matematikai eredményt a $0\leq n\leq20$ tartományban ígér. A 20! még elfér egy előjel nélküli, 64 bites egészben; a 21! már nem.

Az A64 MUL az eredmény alsó 64 bitjét adja vissza. Ezért a tartomány túllépése nem automatikus túlcsordulási hibajelzéshez, hanem modulo $2^{64}$ eredményhez vezet. Az alábbi függvény nem végez külön tartományellenőrzést; a tesztprogram csak megengedett bemeneteket ad át.

8.4.3.1 Assembly-megvalósítás

A fájl neve: lab-a030-rec.s. A blokk összes utasítása és regisztere A64-kontextusú. A ponttal kezdődő elemek GNU assembler-direktívák az AArch64 ELF-célhoz, nem processzorutasítások.

// A64 ISA, ARMv8-A; AArch64 Linux, little-endian.
.arch armv8-a
.text
.p2align 2

.global lab_fact
.type lab_fact, %function
lab_fact:
    .cfi_startproc

    STP     X29, X30, [SP, #-32]!
    .cfi_def_cfa_offset 32
    .cfi_offset 29, -32
    .cfi_offset 30, -24

    MOV     X29, SP
    STR     X19, [SP, #16]
    .cfi_offset 19, -16

    MOV     X19, X0
    CMP     X0, #1
    B.LS    lab_fact_base

    SUB     X0, X0, #1
    BL      lab_fact
    MUL     X0, X0, X19
    B       .Lfact_return

lab_fact_base:
    MOV     X0, #1

.Lfact_return:
    LDR     X19, [SP, #16]
    .cfi_restore 19

    LDP     X29, X30, [SP], #32
    .cfi_restore 29
    .cfi_restore 30
    .cfi_def_cfa_offset 0

    RET
    .cfi_endproc
.size lab_fact, .-lab_fact

.section .note.GNU-stack,"",@progbits

Az A64 CMP utáni B.LS előjel nélküli „kisebb vagy egyenlő” feltételt vizsgál. Előjeles bemenetkezelést ebből nem szabad kikövetkeztetni: például a C-ben negatív értékből uint64_t-ra alakított argumentum igen nagy pozitív egész lehet.

Az aktiváció kerete:

Eltolás az aktuális A64 `SP`-hez képest	Méret	Tartalom
`+0`	8 bájt	A hívó mentett `X29` értéke
`+8`	8 bájt	Az aktiváció mentett visszatérési címe, `X30`
`+16`	8 bájt	A belépéskor kapott `X19` érték
`+24`	8 bájt	Nem használt igazítási hely

A 32 bájtos keret megőrzi a 16 bájtos veremigazítást. Az aktuális $n$ az A64 X19 regiszterben él; a verembe mentett X19 nem az aktuális $n$ , hanem a hívó megőrzendő értéke.

A GNU .cfi_* direktívák hívási keretinformációt (Call Frame Information, CFI) írnak le a hibakereső számára. A kanonikus keretcím (Canonical Frame Address, CFA) itt a belépési veremmutató. A keretfoglalás után ez az aktuális A64 SP + 32; ehhez képest például a mentett X30 eltolása -24. A CFI nem ment regisztert, csak leírja a valódi mentést.

Immediate-ok: a STP/LDP ±32, a STR/LDR #16 eltolása, a #1 konstansok és a helyi ugráscélok mind kódolhatók (lásd az A64 immediate-korlátok összefoglalóját).

8.4.3.2 C-tesztprogram

A fájl neve: lab-a030-main.c.

/* AArch64 Linux célprogram; little-endian profil. */
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

extern uint64_t lab_fact(uint64_t n);

int main(void)
{
    uint64_t result = lab_fact(5);

    printf("5! = %" PRIu64 "\n", result);

    if (result != UINT64_C(120) ||
        lab_fact(0) != UINT64_C(1) ||
        lab_fact(1) != UINT64_C(1) ||
        lab_fact(20) != UINT64_C(2432902008176640000)) {
        fputs("teszthiba\n", stderr);
        return 1;
    }

    puts("tesztek: rendben");
    return 0;
}

8.4.3.3 Összeszerelés, linkelés és futtatás

Az Ubuntu 24.04 alapprofilon, qemu-user célhoz:

# Host: Ubuntu 24.04 x86_64; target: AArch64 little-endian, qemu-user.
aarch64-linux-gnu-as -EL -g -march=armv8-a \
    -o lab-a030-rec.o lab-a030-rec.s

aarch64-linux-gnu-gcc -std=c17 -O0 -g -mlittle-endian \
    -fno-omit-frame-pointer -Wall -Wextra \
    -c lab-a030-main.c -o lab-a030-main.o

aarch64-linux-gnu-gcc -static -no-pie -mlittle-endian \
    lab-a030-main.o lab-a030-rec.o -o lab-a030

qemu-aarch64 ./lab-a030
printf 'kilepesi allapot: %d\n' "$?"

Várt, nem itt mért eredmény: a program 5! = 120, majd tesztek: rendben sort ír ki; kilépési állapota 0. A 1 állapot eredményeltérést jelent. A statikus linkeléshez szükséges céloldali C-könyvtár rendelkezésre állását a laborban kell ellenőrizni.

8.4.4 A híváslánc megfigyelése GDB-vel

Az első lab_fact(5) számításban az argumentumok sorrendje 5, 4, 3, 2, 1. Mivel a keretfoglalás a bázisvizsgálat előtt történik, a legmélyebb ponton öt, egyenként 32 bájtos keret él.

Első terminál, qemu-user cél, elkülönített laborban:

qemu-aarch64 -g 1234 ./lab-a030

Második terminál; a GDB az AArch64 célfolyamathoz kapcsolódik:

gdb-multiarch -q ./lab-a030 \
    -ex 'set pagination off' \
    -ex 'target remote localhost:1234' \
    -ex 'tbreak *lab_fact' \
    -ex 'continue' \
    -ex 'set $lab_entry_sp = (unsigned long)$sp' \
    -ex 'break *lab_fact_base' \
    -ex 'continue' \
    -ex 'p/d $lab_entry_sp - (unsigned long)$sp' \
    -ex 'info registers x0 x19 sp x29 x30' \
    -ex 'bt'

A *lab_fact az első utasításon állít meg, még a prológus előtt. Ez fontos: egy forrásszintű függvény-töréspontot a debugger a prológus utánra is helyezhetne.

Várt ellenőrzési feltételek a báziság elején:

Megfigyelés	Levezetett érték
A64 `X0`	`1`
A64 `X19`	`1`
Belépési és aktuális A64 `SP` különbsége	160 bájt
Aktív faktoriális-aktivációk száma	5
A következő, nem rekurzív hívó	`main`

A visszahívási láncot (backtrace) a GDB bt parancsa jeleníti meg. A pontos címek, sorszámok és a lab_fact_base címke megjelenítése eszközverzió-függő; öt faktoriális-aktiváció felismerése az ellenőrzési cél. Visszatérési címeknél a hibakereső a hívóhely környezetét mutathatja, nem feltétlenül a várt forrássort.

Vizsgálat után a GDB disable breakpoints, majd continue parancsával hagyható lefutni a teljes teszt. Várt kilépési állapot: 0.

8.4.5 Levezetés: mekkora rekurziós mélység fér el?

Jelölje:

$S$ a vizsgált veremkeretet, bájtban;
$R$ a már használt területre és biztonsági tartalékra félretett mennyiséget, bájtban;
$F$ egy rekurzív aktiváció többlet-veremigényét, bájt/aktiváció egységben;
$d$ az egyszerre aktív rekurzív aktivációk számát.

Állandó keretméret mellett szükséges:

$R+dF\leq S.$

Így a modell szerinti maximális mélység:

$d_{\max}=\left\lfloor\frac{S-R}{F}\right\rfloor, \qquad S\geq R,\quad F>0.$

Elméleti, levezetett példa: ha $S=65536$ bájt, $R=4096$ bájt és $F=32$ bájt/aktiváció, akkor:

$d_{\max}=\frac{65536-4096}{32}=1920.$

Ez nem állítás a Linux alapértelmezett veremméretéről, és nem mért QEMU-határ. A ténylegesen használható tartományt befolyásolhatja a folyamat veremkorlátja, a kezdeti argumentum- és környezetterület, a hívók kerete, valamint például a jelkezelés helyigénye. A tartalékot a konkrét programra kell megválasztani.

A saját assembly-függvényünkben:

lab_fact(0) és lab_fact(1) egy aktivációt használ;
lab_fact(n) pozitív $n$ mellett $n$ aktivációt használ;
a rekurzív rész csúcsidejű veremigénye ezért pozitív $n$ esetén $32n$ bájt.

A pontos faktoriális megengedett legnagyobb argumentuma, 20, csak 640 bájtot igényel ebben a függvényben. Az aritmetikai tartományhatár és a veremkapacitás két külön korlát.

Ha a báziság nem érhető el, a veremmutató minden aktivációval tovább csökken. A verem kimerülésének (stack overflow) tipikus Linux-tünete SIGSEGV, gyakran a következő keret mentésekor. Az ISA nem ír elő külön „rekurziós túlcsordulás” kivételt. A hibát célszerű néhány aktiváció megfigyelésével felismerni, nem szándékosan a teljes verem elfogyasztásáig futtatni.

8.4.6 Farokhívás: mit nem végez el az assembler?

A farokhívás (tail call) olyan hívás, amely után a hívóban már nem marad elvégzendő számítás; a hívott függvény eredménye közvetlenül továbbadható.

A példánk önhívása nem farokhívás: visszatérés után még meg kell szorozni az eredményt az aktuális $n$ értékkel.

Akkumulátor bevezetésével viszont használható az

$g(n,a)=g(n-1,n\cdot a)$

átmenet, $n\leq1$ esetén $a$ eredménnyel. Ez ciklussá alakítható.

A GNU assembler nem végez automatikus farokrekurzió-optimalizálást: utasításokat és relokációkat állít elő, nem alakítja át magas szinten az algoritmust. Ha A64 BL utasítást írunk, abból nem lesz magától keret nélküli ciklus. A puszta BL → B csere sem általános megoldás: a keretet és a visszatérési címet is helyesen kell kezelni.

8.4.7 Tipikus hibák és célzott ellenpróbák

Tünet	Hipotézis	Adatgyűjtés és egyetlen javítás
Az eredmény hibás, de a program visszatér	Az aktuális $n$ hívás által felülírható regiszterben maradt	GDB-ben hasonlítsd össze hívás előtt és után; használj megfelelően mentett A64 `X19`-et
A visszatérés ugyanazon utasításokhoz vezet	Elveszett a külső aktiváció A64 `X30` értéke	Vizsgáld a mentett címet; javítsd a mentés–visszatöltés párt
Ugyanaz az argumentum ismétlődik, miközben fogy a verem	Nincs előrehaladás a báziseset felé	Állj meg két egymást követő belépésnél; javítsd a csökkentést
A számítás jó, a backtrace hibás	A CFI nem egyezik a kerettel	Hasonlítsd össze a leírt és tényleges eltolásokat; csak a hibás CFI-adatot módosítsd

A gépi kód és a keretleírás vizsgálata, AArch64 qemu-user célállományon:

aarch64-linux-gnu-objdump -d lab-a030-rec.o
aarch64-linux-gnu-readelf --debug-dump=frames lab-a030-rec.o

8.4.8 Feladatok

(magyarázó, alapszint — cél: megértés-ellenőrzés) Hány faktoriális-keret él a 0, 1 és 5 bemenet legmélyebb pontján? A 5 bemenet legbelső aktivációjában milyen értéket őriz a mentett A64 X19 helye?
(implementációs, középszint — cél: rutinépítés) Írj lab_fact_loop nevű, akkumulátoros A64 változatot keretfoglalás nélkül. Ellenőrizd a rekurzív változattal való egyezését 0 és 20 között.
(becslési, alapszint — cél: megértés-ellenőrzés) Egy 96 KiB-os veremkeretből 8 KiB tartalékot hagysz. Hány 32 bájtos aktiváció fér el a modell szerint?
(hibakeresési, középszint — cél: rutinépítés) A rekurzív változat csökkentő utasításában a #1 értéket változtasd #0-ra. Újraépítés után állíts töréspontot a függvény első utasítására. Legfeljebb három belépésből diagnosztizáld a hibát; ne futtasd veremkimerülésig.

8.4.9 Megoldások

1. megoldás — Segítség. Számold meg, hány önhívás történik, mielőtt a báziseset ( $n \le 1$ ) teljesül — ez adja a keretek számát. A mentett X19 a HÍVÓ aktiváció $n$ -je, nem a jelenlegié.

1. megoldás — Teljes megoldás. A keretszám rendre 1, 1, 5. A legbelső aktiváció aktuális A64 X19 értéke 1, de a mentett helyen 2 található: ezt használja majd a közvetlen hívó a saját szorzásához.

2. megoldás — Segítség. Egyetlen akkumulátorregiszter és egy ciklus elég; nincs szükség STP/LDP-re vagy BL-re, mert a függvény nem hív mást és nem nyúl callee-saved regiszterhez.

2. megoldás — Teljes megoldás. Az alábbi függvény a lab-a030-rec.s végére illeszthető. Minden utasítása és regisztere A64-kontextusú; a direktívák GNU assembler-direktívák.

// A64 ISA, ARMv8-A; ugyanazon labor forrásfájljának kiegészítése.
.text
.p2align 2
.global lab_fact_loop
.type lab_fact_loop, %function
lab_fact_loop:
    .cfi_startproc
    MOV     X1, #1

.Lloop:
    CMP     X0, #1
    B.LS    .Lloop_done
    MUL     X1, X1, X0
    SUB     X0, X0, #1
    B       .Lloop

.Lloop_done:
    MOV     X0, X1
    RET
    .cfi_endproc
.size lab_fact_loop, .-lab_fact_loop

A függvény nem hív másik függvényt, nem módosít megőrzendő általános regisztert, ezért nincs szüksége keretre. Az A64 X30 érintetlen marad. A C-fájlban deklaráld a uint64_t lab_fact_loop(uint64_t n) függvényt, és hasonlítsd össze mind a 21 bemenet eredményét a lab_fact eredményével. A korábbi assemble–compile–link–run parancssort ismételve a várt kilépési állapot továbbra is 0.

3. megoldás — Segítség. Alakítsd mindkét mennyiséget bájtra (1 KiB = 1024 bájt), vond ki a tartalékot a teljes keretből, majd oszd el az egy aktivációra jutó mérettel.

3. megoldás — Teljes megoldás. Mivel 1 KiB = 1024 bájt:

$d_{\max}=\frac{(96-8)\cdot1024}{32}=2816.$

Ez a megadott modell korlátja, nem garantált üzemi határ.

4. megoldás — Segítség. Ha a csökkentés #0, az X0 érték két egymást követő belépés között azonos marad — ez a báziseset felé vezető előrehaladás hiánya, nem a bázisfeltétel hibája.

4. megoldás — Teljes megoldás. A hibás programban minden belépésnél A64 X0 = 5, miközben az SP két egymást követő belépés között 32 bájttal csökken. Ez az előrehaladás hiányát mutatja. A SUB immediate-jét állítsd vissza #1-re, majd újraépítés után ellenőrizd a 5, 4, 3, 2, 1 sorozatot és a 120 eredményt.

8.4.10 Rövid összefoglaló

A rekurzív A64 függvény ugyanazt a kódot hajtja végre több, elkülönített állapotú aktivációban. Az önhívás felülírja a visszatérési címet, az eredményregiszter pedig nem őrzi meg automatikusan az eredeti argumentumot. Ezért a mentések és visszatöltések minden szinten szükségesek. A báziseset mellett a felé vezető előrehaladást is ellenőrizni kell. Állandó keretméretnél a rendelkezésre álló veremből egyszerű mélységbecslés adható, de az üzemi tartalék környezetfüggő. A GDB backtrace és a veremmutató változása együtt jól ellenőrizhetővé teszi a hívásláncot.

Aktiváció: egy még be nem fejezett függvényvégrehajtás.
Rekurziós mélység: az egyszerre aktív rekurzív aktivációk száma.
Farokhívás: hívás, amely után nem marad további eredményfeldolgozás.

8.4.11 Források és ellenőrzési hiányok

A linkek és a dokumentumverziók közös állapota az Olvasói útmutató forrásállapot-táblájában van; itt csak az alfejezet saját megállapításai szerepelnek.

AAPCS64 – Arm hivatalos ABI-dokumentum — regisztermegőrzés, veremigazítás, keretrekord. Tartalmilag ellenőrizve: a jelenlegi kiadás 2025Q4 (2026-01-23), Release minőségű (csak az SME-részek Beta).
Arm A-profile architektúra-dokumentáció — A64 utasításszemantika és kódolási korlátok. Ellenőrizve: a link él; a fejezetszám és a kiadásbetű az Arm-oldalak közös korlátja miatt nem ellenőrzött.
GNU assembler kézikönyv — AArch64-szintaxis és CFI-direktívák. Tartalmilag ellenőrizve: a jelenlegi kiadás binutils 2.47.
GDB kézikönyv — távoli hibakeresés, keretek és backtrace. Tartalmilag ellenőrizve, de verzió-megjegyzéssel: a „current” fejlesztői pillanatkép (közös verziókorlát).

Ellenőrzési hiányok, amelyek a fenti ellenőrzés után is ténylegesen fennmaradnak: a kódot és parancsokat itt nem futtattuk. A csomagolt eszközverziókat, a statikus linkelés feltételeit és a backtrace konkrét megjelenését a hallgatói laborban kell ellenőrizni. A veremértékek levezetett adatok; tényleges veremkimerülési határt nem mértünk.