# It turns out that we were recomputing fibonacci numbers starting at
# F(2) in our for loop.  We just need to change that to start at the
# first index for which we haven't already computed the fibonacci
# number, which will be the end of fibs.

# if we run "python fibonacci_8.py", we'll see that we've fixed the code!

fibs = [0, 1]
def fibonacci(n):
    """
    Return the n_th Fibonnaci number $F_n$.  The Fibonacci sequence
    starts 0, 1, 1, 2, 3, 5, 8, ..., and is defined as
    $F_n = F_{n-1} + F_{n-2}.$

    >>> fibonacci(0)
    0
    >>> fibonacci(5)
    5
    >>> fibonacci(10)
    55
    >>> fibonacci(-1)
    Traceback (most recent call last):
    ...
    ValueError: n must be a non-negative integer
    >>> fibonacci(2.3)
    Traceback (most recent call last):
    ...
    ValueError: n must be a non-negative integer
    >>> fibonacci('a')
    Traceback (most recent call last):
    ...
    ValueError: n must be a non-negative integer
    """
    if not isinstance(n, int):
        raise ValueError('n must be a non-negative integer')
    if n < 0:
        raise ValueError('n must be a non-negative integer')                
    if len(fibs) >= n:
        return fibs[n]
    for i in range(len(fibs), n+1):
        fibs.append(fibs[i-1] + fibs[i-2])
    return fibs[n]

if __name__ == '__main__':
    import doctest
    doctest.testmod()

# It turns out that we were recomputing fibonacci numbers starting at
# F(2) in our for loop.  We just need to change that to start at the
# first index for which we haven't already computed the fibonacci
# number, which will be the end of fibs.

# if we run "python fibonacci_8.py", we'll see that we've fixed the code!

fibs = [0, 1]
def fibonacci(n):
    """
    Return the n_th Fibonnaci number $F_n$.  The Fibonacci sequence
    starts 0, 1, 1, 2, 3, 5, 8, ..., and is defined as
    $F_n = F_{n-1} + F_{n-2}.$

    >>> fibonacci(0)
    0
    >>> fibonacci(5)
    5
    >>> fibonacci(10)
    55
    >>> fibonacci(-1)
    Traceback (most recent call last):
    ...
    ValueError: n must be a non-negative integer
    >>> fibonacci(2.3)
    Traceback (most recent call last):
    ...
    ValueError: n must be a non-negative integer
    >>> fibonacci('a')
    Traceback (most recent call last):
    ...
    ValueError: n must be a non-negative integer
    """
    if not isinstance(n, int):
        raise ValueError('n must be a non-negative integer')
    if n < 0:
        raise ValueError('n must be a non-negative integer')                
    if len(fibs) >= n:
        return fibs[n]
    for i in range(len(fibs), n+1):
        fibs.append(fibs[i-1] + fibs[i-2])
    return fibs[n]

if __name__ == '__main__':
    import doctest
    doctest.testmod()

# It turns out that we were recomputing fibonacci numbers starting at # F(2) in our for loop.  We just need to change that to start at the # first index for which we haven't already computed the fibonacci # number, which will be the end of fibs. # if we run "python fibonacci_8.py", we'll see that we've fixed the code! Return the n_th Fibonnaci number $F_n$.  The Fibonacci sequence     starts 0, 1, 1, 2, 3, 5, 8, ..., and is defined as     $F_n = F_{n-1} + F_{n-2}.$      >>> fibonacci(0)     0     >>> fibonacci(5)     5     >>> fibonacci(10)     55     >>> fibonacci(-1)     Traceback (most recent call last):     ...     ValueError: n must be a non-negative integer     >>> fibonacci(2.3)     Traceback (most recent call last):     ...     ValueError: n must be a non-negative integer     >>> fibonacci('a')     Traceback (most recent call last):     ...     ValueError: n must be a non-negative integer