## Post Lab 11

Fibonacci Numbers

Any code that can be written using recursion can be written using loops. However, sometimes it is easier to program an algorithm using recursion. One case when it is easier to program an algorithm recursively is when it is defined recursively. For example, the Fibonacci sequence is a well-known mathematical sequence in which each term is the sum of the two previous terms. Because the Fibonacci sequence is defined recursively, it is natural to write a recursive function to determine the nth number in the sequence.

#### Details

Create a file fibonacci.py, and write a function fibonacci(n) in this file. This function should recursively compute the nth fibonacci number. If fib(n) is the nth term of the sequence, then the sequence can be defined as follows:

$\begin{eqnarray} fib(0) &=& 0\\ fib(1) &=& 1\\ fib(n) &=& fib(n - 1) + fib(n - 2) \mbox{ for all n greater than 1} \end{eqnarray}$

#### Example

>>> fibonacci(0)
0
>>> fibonacci(1)
1
>>> fibonacci(2)
1
>>> fibonacci(3)
2
>>> fibonacci(4)
3
>>> fibonacci(5)
5


### Submission

Please submit your Python file to inquire by the beginning of class on Monday, Feb. 22nd