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 FibonacciSequence
	**Prints the nth fibonacci number**
 
	on start
 
		args := program arguments
 
		if args empty
			print .fibonacci(8)
 
		else
 
			try
				print .fibonacci(integer.parse(args[0]))
 
			catch FormatException
				print to Console.error made !, "Input must be an integer"
				exit program with error code
 
			catch OverflowException
				print to Console.error made !, "Number too large"
				exit program with error code
 
	define fibonacci(n as integer) as integer is shared
		**Returns the nth fibonacci number**
 
		test
			assert fibonacci(0) = 0
			assert fibonacci(1) = 1
			assert fibonacci(2) = 1
			assert fibonacci(3) = 2
			assert fibonacci(4) = 3
			assert fibonacci(5) = 5
			assert fibonacci(6) = 8
			assert fibonacci(7) = 13
			assert fibonacci(8) = 21
 
 
		body
			a, b := 0, 1
 
			for n
				a, b := b, a + b
 
			return a
 