Recursion and Array Examples

CS 301 Lecture, Dr. Lawlor

Here's a recursive implementation of Fibonacci in C++:

int fib(int n) {
	if (n<2) return 1; /* base case */
	else return fib(n-1) + fib(n-2);
}

int foo(void) {
	return fib(10);
}

(Try this in NetRun now!)

And now in assembly. This version stores things in preserved registers:

mov rdi,10
call fib  ; call fib function with one parameter, 10
ret

; fib function: takes one integer, returns value of Fibonacci sequence there
fib:
	cmp rdi,2
	jl return_one ; check for recursion base case
	
	push r15 ; need preserved registers to stash arguments
	push r13
	mov r15,rdi ; save our rdi (fib will change it)
	sub rdi,1
	call fib   ;  call fib(n-1)
	mov r13,rax ; save returned value
	
	mov rdi,r15 ; restore n
	sub rdi,2
	call fib  ; call fib(n-2)
	add rax,r13 ; add returned value with previous return
	pop r13 ; restore preserved registers
	pop r15
	ret

	return_one: ; recursion base case:
		mov rax,1
		ret

(Try this in NetRun now!)

This version (developed in class) stores temporary values on the stack:

mov rdi,10
call fib  ; call fib function with one parameter, 10
ret

; fib function: takes one integer, returns value of Fibonacci sequence there
fib:
	cmp rdi,2
	jl return_one ; check for recursion base case
	
	sub rdi,1
	push rdi ; save rdi (fib will change it)
	call fib   ;  call fib(n-1)
	pop rdi  ; restore our argument
	
	sub rdi,1 ; second subtraction (now equals n-2)
	push rax ; save first fib's return value
	call fib  ; call fib(n-2)
	pop rcx ; restore first fib's value to rcx
	add rax,rcx ; add both return values
	ret

	return_one: ; recursion base case:
		mov rax,1
		ret

(Try this in NetRun now!)

Here's a non-recursive version that stores the Fibonacci entries to an array, allocated on the stack:

push r15 ; save registers
push r14
extern read_input
call read_input
; rax contains "n", the number of terms to print
movsxd rax,eax ; promote 32-bit return value to 64-bit
cmp rax,0
jle flee_in_terror
mov r15, rax ; n
imul rax,4
sub rsp,rax ; make room for 4*n bytes
mov r14,rsp ; array starts at r14

mov DWORD[r14],1; array[0]=1
cmp r15,1
jle skip_lotsa_stuff
mov DWORD[r14+4],1; array[1]=1

mov rax,2 ; i
jmp loop_compare
startoloop:
	mov ecx,DWORD[r14+4*rax-8] ; array[i-2]
	mov edx,DWORD[r14+4*rax-4] ; array[i-1]
	add ecx,edx
	mov DWORD[r14+4*rax],ecx ; array[i] = array[i-1]+array[i-2]

	add rax,1
	loop_compare:
	cmp rax,r15
	jl startoloop

skip_lotsa_stuff:

mov rdi,r14 ; ptr
mov rsi,r15 ; num elements
extern iarray_print
call iarray_print

mov rax,r15
imul rax,4
add rsp,rax

flee_in_terror:
pop r14 ; restore registers
pop r15
ret

(Try this in NetRun now!)