Rekurzió

Az alábbiakban egy konkrét példán mutatjuk be, hogy egy önmagát rekurzívan hívó függvény hogyan használja a vermet.

Példaként tekintsük azt a programot, amely a rekurzív definíciója szerint számítja ki a Fibonacci sorozat n-dik elemét.

				F(0) := 0
				F(1) := 1
				F(n) := F(n-1) + F(n-2), ha n>1
			

Vagyis:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

global _Fibon
section .text

_Fibon:
    push  ebp
    mov   ebp, esp
    push  ecx
    mov   eax, [ ebp + 8 ]   ;N-t kivesszuk a verembol
	cmp   eax, 1
	jbe   nincs_rekurzio
	dec   eax
	push  eax
	dec   eax
	push  eax
	call  _Fibon
	add   esp,4
	mov   ecx, eax
	call  _Fibon
	add   esp,4
	add   eax, ecx

nincs_rekurzio:
	pop   ecx
    pop   ebp
    ret

1
2
3
4
5
6
7
8
9

#include "stdio.h"

int main( void ) {
    unsigned int n;
    printf( "Meddig szamoljuk ki a fibonacci szamot? " );
    scanf( "%d", &n );
    printf( "Az eredmeny: %u", Fibon( n ) );
}

Vizsgáljuk meg, hogy ha a C főprogramból meghívjuk a Fibon függvényt n-3-re, akkor hogyan alakul a verem tartalma!

A C főprogram a verembe helyezi a függvény paraméterét, majd meghívja a szubrutint, végül a visszatérés után kitakarítja a verembe tett paramétert. Ezt a következő utasítássorozat végzi:

Mire az assembly szubrutinhoz kerül a vezérlés, a veremtartalom így fog kinézni:

Ha jól írtuk meg a programot, akkor az ecx-be az az érték kerül vissza, amely korábban éppen az ecx-ből került a verembe, és az ebp-be is az, amely az ebp-ből került a verembe, továbbá olyan címet vesz ki a ret és értelmez visszatérési címkként, amely egy call utasítás által került a verembe. Ha nem így lenne, akkor valószínűleg valami hibát vétettünk a program tervezésekor, és a program nem fog működni.

Most nem hibás a programunk, ezért a két pop utáni ret a 16. sorba vezeti a programot. Eddigre a verem tartalma a következőképpen néz ki. (Ne felejtsük el, hogy a veremből kivétel (pop és ret) csak kimásolja az adatokat a megfelelő regiszterekbe, és az esp értékét aktualizálja, de a memóriából az adatok ténylegesen nem törlődnek, ezért a veremmutató által jelzett "verem teteje" feletti adatok bizonytalan ideig még elérhetőek. Ezt halványszürke betűkkel jeleztük)

Az eax-be kiolvasódik az ebp+8 címről a legutóbbi VTC előtt verembe tett érték, vagyis eax=0 lesz. Erre a jbe feltétele teljesül, vagyis a nincs_rekurzio cimkéhez ugrunk.

Most a verem tetején lévő érték ecx-be másolódik, és a verem mutató egy sorral lejjebbi értéket fog mutatni (=néggyel nő). A pop ebp hatására a verem aktuális teteje az ebp-be másolódik, és az esp újabb 4-gyel nő. Végül a ret a verem jelenlegi tetején lévő adatot címként értelmezi, és erre a címre ugrik.

Végeredményként a ret után ez a helyzet áll elő (és ne felejtsük el, hogy közben eax=0, vagyis ezt a 0 értéket adjuk vissza _Fibon(0)-ra):

A C főprogram tehát a regiszterekből csak annyit lát, hogy az eax-ben előállt a Fibon(3) értéke, de minden más használt regiszter (az ebp és az ecx is) ugyanazt az értéket tartalmazza, mint kezdetben. Az assembly függvényünk tehát maradéktalanul teljesíti feladatát: csak azt a regisztert módosítja, amelyben az eredményt elő kell állítania, minden más értéket változatlanul hagy.