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


 
class
	APPLICATION
 
create
	make
 
feature
 
	fibonacci (n: INTEGER): INTEGER
		require
			non_negative: n >= 0
		local
			i, n2, n1, tmp: INTEGER
		do
			n2 := 0
			n1 := 1
			from
				i := 1
			until
				i >= n
			loop
				tmp := n1
				n1 := n2 + n1
				n2 := tmp
				i := i + 1
			end
			Result := n1
			if n = 0 then
				Result := 0
			end
		end
 
feature {NONE} -- Initialization
 
	make
			-- Run application.
		do
			print (fibonacci (0))
			print (" ")
			print (fibonacci (1))
			print (" ")
			print (fibonacci (2))
			print (" ")
			print (fibonacci (3))
			print (" ")
			print (fibonacci (4))
			print ("%N")
		end
 
end
 