#!/usr/bin/env python3

def fibonacci(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for i in range(2, n+1):
        a, b = b, a+b
    return b


def fibonacci2(n):
    fib = [0, 1]
    while len(fib) <= n:
        fib.append(fib[-1] + fib[-2])
    return fib[n]


def fibonacci3(n):
    if n <= 1:
        return n
    else:
        return fibonacci3(n-1) + fibonacci3(n-2)