CSCI 264 – Assembly Language
Recursion: Fibonacci Numbers
fib(n)= 1, n<2
fib(n)= fib(n-1)+fib(n-2), n>=2
fragment of C++ code:
…
extern “C” int fib(int n);
….
int n, result;
cin > n;
result = fib(n);
cout < result;
assembly code for function fib
global fib
fib: push ecx
mov eax, [esp+8]
cmp eax, 2
jae els
mov eax, 1
jmp dun
els: dec eax
mov ecx, eax
push eax
call fib
add esp, 4
dec ecx
push ecx
mov ecx, eax
call fib
add esp, 4
add eax, ecx
dun: pop ecx
ret
Address ( assume ESP= 100 at the initial point) / value / explanation76: ESP after PUSH ECX / 01
inside the fib for n = 1 / 00
00
00
80: ESP after CALL fib / EE / The address of ADD ESP, 4 in function
the address of return / EE / fib for n = 2 was pushed inside
statement pushed into / EE
Stack / EE
84: ESP after PUSH EAX / 01 / EAX was decremented by 1 and pushed
inside the function fib / 00 / inside the stack, this will be the parameter
for n = 2 / 00 / for the recursive call fib(n-1) ( fib (1))
00
88: ESP after PUSH ECX / ** / function fib: garbage that was in ECX
in function fib / ** / was pushed inside the stack
**
**
92: ESP after the address of / FF / address of cout < result from main ( C++)
the return statement / FF
FF
FF
96: ESP after inserting / 02 / n =2 , function call from main (C++) with
parameter in C++ main / 00 / parameter n =2
00
00
100: ESP initial value
MOV EAX, [ESP+2] ; EAX gets 2
CMP EAX, 2 JAE ELS ; EAX =2 there is a jump to els
ELS: DEC EAX ; EAX gets 1
MOV ECX, EAX ; ECX gets 1
PUSH EAX CALL fib ; the function will return to the beginning of fib
;with parameter 1
…..; now we are inside function fib again with parameter 1
PUSH ECX ; ECX equals 1
MOV EAX, [ESP+8] ; EAX gets 1
CMP EAX, 2
JAE ELS ; no jump this time
MOV EAX, 1 ; EAX gets 1 – this is the return value for fib(1)
JMP DUN
……
DUN: POP ECX ; ECX gets 1
RET ; return to the caller function
; the execution came back to fib with n = 2 to the line ADD ESP, 4
…………; after we came back from the n =1 to n=2
ADD ESP, 4
DEC ECX ; ECX gets 0 ( n-2)
PUSH ECX ;the value at the top of the stackis 00 00 00 00
MOV ECX, EAX ; ECX gets 1
;( ECX will keep the value of
;fib ( n-1): fib(1) in our case)
CALL fib ; returned address pushed
………..; now we are inside function fib again with parameter 0
PUSH ECX ; ECX is 1, the top value is 01 00 00 00
MOV EAX, [ESP+8] ; EAX gets 0
CMP EAX, 2 JAE ELS ; no jump
MOV EAX, 1 ; EAX gets 1
JMP DUN
………..
DUN: POP ECX ; ECX gets 1
RET
; return to fib with n = 2 to the line add esp, 4 after the second call to fib
ADD ESP, 4 ; ESP = ESP + 4
ADD EAX, ECX ; EAX = EAX +ECX = 1
;(EAX is 1 – the value of fib(2) = fib(0) + fib(1)
;ECX is 1 ECX kept the value of fib(1))
POP ECX
RET
After the execution will return to main in C++ the command ADD ESP, 4 will be executed in the “ background”
Example:
n!= 1 , n =0
n! = n*(n-1)! , n >0
global fact
fact: push ecx
move eax, [esp+8]
cmp eax, 0
ja els
move eax, 1
jmp dun
els: mov ecx, eax
dec eax
push eax
call fact
add esp, 4
mul ecx
dun: pop ecx
ret