4/11/08

MIPS Recursive Fibonacci

As you may seen I posted an implementation of Fibonacci in C(recursive and not).
I have also posted Mips Non Recursive Fibonacci.
Here is the recursive implementation of Fibonacci for MIPS. I have already told this, I suggest you use SPIM to simulate your MIPS programs first.

.data
msg1:.asciiz "Give a number: "
.text
.globl main
main:

li $v0,4
la $a0,msg1
syscall #print msg
li $v0,5
syscall #read an int
add $a0,$v0,$zero #move to $a0

jal fib #call fib

add $a0,$v0,$zero
li $v0,1
syscall

li $v0,10
syscall

fib:
#a0=y
#if (y==0) return 0;
#if (y==1) return 1;
#return( fib(y-1)+fib(y-2) );

addi $sp,$sp,-12 #save in stack
sw $ra,0($sp)
sw $s0,4($sp)
sw $s1,8($sp)

add $s0,$a0,$zero

addi $t1,$zero,1
beq $s0,$zero,return0
beq $s0,$t1,return1

addi $a0,$s0,-1

jal fib

add $s1,$zero,$v0 #s1=fib(y-1)

addi $a0,$s0,-2

jal fib #v0=fib(n-2)

add $v0,$v0,$s1 #v0=fib(n-2)+$s1
exitfib:

lw $ra,0($sp) #read registers from stack
lw $s0,4($sp)
lw $s1,8($sp)
addi $sp,$sp,12 #bring back stack pointer
jr $ra

return1:
li $v0,1
j exitfib
return0 : li $v0,0
j exitfib

19 comments:

Anonymous said...

Thanks very much :)

Anonymous said...

very good thank you for your help!!!

Anonymous said...

Hey this block of code is really cool.... helped me a lot..... Thanks so much for uploading....!!!

- TS

Unknown said...

Thank you very much for your code! i really enjoyed testing it.

Anonymous said...

thanx a lot... It helped me a lot

Anonymous said...

thanks a lot bro (:

Anonymous said...

Is there a way to print all the numbers until 'n' with this recursive solution?

Andreas Papadopoulos said...

Hello,
First of all thank you for visiting and reading my blog.
The above program return the fib(n).
When you give n and you want to print all the numbers you have to change the function to print every number calculated in fib depending on what order you want to print.
For example you can add on line 45 to print $s1 which contains the fib (y-1). or you can print $v0 on line 49.
I didn't try it but I am pretty sure it will work.
Good luck and thank you.

Anonymous said...

Hey,
thanks for ur programm, works nice. But i have one problem to understand it, would be nice if u could help me out.

in line 42 u jump to the fib-label and save the adress of line 44. it will go on with line 44, when the exitfib label is called from label return1. but return 1 writes a 1 in register v0. i wonder why then in line 44 u have fib(n-1) instead of 1(which was wrote in v0 by return1). i hope my english is understandable, would be nice to hear from u.
greetings

Andreas Papadopoulos said...

Hello,
Thank you for visiting my blog and for your comment too!

When you call fib on line 42 you want to get the fib(n-1). that is when it returns you have on $v0 the fib(n-1). if you add one you will loose the result. 1 is only the first time when recursion starts unrolling. After the first time you won't have 1 on $v0.

That is when the program reaches line 44 you have successfully calculate fib(y-1) an then on line 48 you call again to calculate fib(y-2). So when you reach line 50 you have fib(y-1) on $s0 an fib(y-2) on $v0. Add them and return the result.

I suggest you run step by step the code and you will notice that if you add 1 on line 44 you will get wrong results as $v0 is not always 1.

I hope that this will help you.
Thank you very much.

Anonymous said...

hey, its me again, hoping not to annoy you.
My problem is, that i dont understand, why in line 44 there is fib(n-1) in $v0. Would be nice, if you could explain me. I think that line 57: jr $ra causes the jump to line 44, right? (Because line 42 jumped and linkes line 44 in $ra) and this is only reached by the return1 label, which says: li $v0, 1. So there would be a 1 in $v0. But how is it possible that you have fib(n-1)?
Need to understand that for university, hope u can help me out and thanks for your last answer.
greetings

Andreas Papadopoulos said...

Hello again,

Line 57 (jr $ra) does not always jump to line 44. It may jump to line 44,50 or 16. At the end of the call on line 42 the whole function ran and calculated fib(n-1). As you can see on line 50 $v0 is by fib(n-2). Your question is the same as why at line 50 $v0 has fib(n-2)? This the recursion process. When you go to line 44 the code below this line was executed in previous recursive calls.
Did you run the code step by step and notice how $v0 changes? You may perhaps try to run it on paper with a small y (e.g. 5).

Thank you for visiting my blog.

Unknown said...

thank you!it helps me so much! it made me crazy!

Nepali fan said...

thx a lot!
i wonder how would u translate this mips code in c++

Andreas Papadopoulos said...

Hello,
Thank you for visiting.
Take a look at:

Fibonacci in C

Anonymous said...

Thanks for the help!!

Anonymous said...

how do you get it to print every number? i tried li $v0,4 and syscall on lines 49 and 50 and still no result help!

Anonymous said...

Hi, can you explain me briefly whats is going on in this code? I understand that the program write on the SP all the iterations, like if you put 7, will be 6 x3 in the stack, but what happen later? (i'm really bad at this)

Unknown said...

thank you bro !