CPSC 170 A

- Location
- Trexler 363
- Times
- MWF 3:30 - 5:30

- Office Hours
- M-Th 6 - 7pm
- Office
- Trexler 365B
- chssmith AT roanoke DOT edu

< Back

## Post Lab 11

#### Details

#### Example

### Submission

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.

Create a file *fibonacci.py*, and write a
function `fibonacci(n)`

in this file. This function
should recursively compute the *n ^{th}* 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. 22^{nd}