The Fibonacci sequence is a sequence    Fn    of natural numbers defined recursively:

      F0 = 0 
      F1 = 1 
      Fn = Fn-1 + Fn-2, if n>1 



Task

Write a function to generate the    nth    Fibonacci number.

Solutions can be iterative or recursive (though recursive solutions are generally considered too slow and are mostly used as an exercise in recursion).

The sequence is sometimes extended into negative numbers by using a straightforward inverse of the positive definition:

      Fn = Fn+2 - Fn+1, if n<0   

support for negative      n      in the solution is optional.



Related tasks

   Fibonacci n-step number sequences‎
   Leonardo numbers


References

   Wikipedia, Fibonacci number
   Wikipedia, Lucas number
   MathWorld, Fibonacci Number
   Some identities for r-Fibonacci numbers
   OEIS Fibonacci numbers
   OEIS Lucas numbers


 
	.text
main:	li	$v0, 5		# read integer from input. The read integer will be stroed in $v0
	syscall
 
	beq	$v0, 0, is1
	beq	$v0, 1,	is1	
 
	li	$s4, 1		# the counter which has to equal to $v0	
 
	li	$s0, 1
	li	$s1, 1
 
loop:	add	$s2, $s0, $s1
	addi	$s4, $s4, 1
	beq	$v0, $s4, iss2
 
	add	$s0, $s1, $s2
	addi	$s4, $s4, 1
	beq	$v0, $s4, iss0
 
	add	$s1, $s2, $s0
	addi	$s4, $s4, 1
	beq	$v0, $s4, iss1
 
	b 	loop
 
iss0:	move	$a0, $s0	
	b	print
 
iss1:	move	$a0, $s1	
	b	print
 
iss2:	move	$a0, $s2	
	b	print
 
 
is1:	li	$a0, 1
	b 	print
 
print:	li	$v0, 1
	syscall
	li	$v0, 10
	syscall
 