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.
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} \]
>>> fibonacci(0) 0 >>> fibonacci(1) 1 >>> fibonacci(2) 1 >>> fibonacci(3) 2 >>> fibonacci(4) 3 >>> fibonacci(5) 5
Please submit your Python file to inquire by the beginning of class on Monday, Feb. 22nd