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:
Thanks very much :)
very good thank you for your help!!!
Hey this block of code is really cool.... helped me a lot..... Thanks so much for uploading....!!!
- TS
Thank you very much for your code! i really enjoyed testing it.
thanx a lot... It helped me a lot
thanks a lot bro (:
Is there a way to print all the numbers until 'n' with this recursive solution?
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.
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
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.
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
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.
thank you!it helps me so much! it made me crazy!
thx a lot!
i wonder how would u translate this mips code in c++
Hello,
Thank you for visiting.
Take a look at:
Fibonacci in C
Thanks for the help!!
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!
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)
thank you bro !
Post a Comment