Silly Ways to find the Nth Fibonacci Number

fibonacci.py

import math
import time

PHI = (1.0 + math.sqrt(5))/2.0


def fibonacci_for(N):
    for_loop = [0]

    def fib(N):
        a = 1
        b = 1
        for i in range(N-2):
            for_loop[0] += 1
            a, b = b, b + a
        return b

    t = time.time()
    Fn = fib(N)
    t = time.time() - t
    return ("For Loop", N, Fn, t, for_loop[0])


def fibonacci_recursive(N):
    recursive = [0]

    def fib(N):
        recursive[0] += 1
        if ((N == 1) or (N == 2)):
            return 1
        else:
            return fib(N-1) + fib(N-2)

    t = time.time()
    Fn = fib(N)
    t = time.time() - t
    return ("Recursive", N, Fn, t, recursive[0])


def fibonacci_recurse_sum(N):
    recurse_sum = [0]

    def fib(N):
        recurse_sum[0] += 1
        if ((N == 1) or (N == 2)):
            return
        else:
            fib(N-1), fib(N-2)
            return

    t = time.time()
    fib(N)
    Fn = int((recurse_sum[0]+1)/2.0)
    t = time.time() - t
    return ("Recursive Sum", N, Fn, t, recurse_sum[0])


def fibonacci_tail(N):
    tail_rec = [0]

    def fib(N, n1, n2):
        tail_rec[0] += 1
        if N == 1:
            return n2
        return fib(N-1, n2, n1 + n2)

    t = time.time()
    Fn = fib(N, 0, 1)
    t = time.time() - t
    return ("Tail Recursive", N, Fn, t, tail_rec[0])


def fibonacci_memoised(N):
    memoised = [0]
    memo = {1: 1, 2: 1}

    def fib(N):
        memoised[0] += 1
        if N in memo:
            return memo[N]
        else:
            f = fib(N-1) + fib(N-2)
            memo[N] = f
            return f

    t = time.time()
    Fn = fib(N)
    t = time.time() - t
    return ("Memoised Recursive", N, Fn, t, memoised[0])


def fibonacci_closed(N):
    closed = [0]

    def fib(N):
        closed[0] += 1
        return int((math.pow(PHI, N) - math.pow(PHI - 1.0, N)) / math.sqrt(5.0))

    t = time.time()
    Fn = fib(N)
    t = time.time() - t
    return ("Closed Form", N, Fn, t, closed[0])


def fibonacci_rounding(N):
    rounding = [0]

    def fib(N):
        rounding[0] += 1
        return int((math.pow(PHI, N) / math.sqrt(5.0)) + 0.5)

    t = time.time()
    Fn = fib(N)
    t = time.time() - t
    return ("Rounding", N, Fn, t, rounding[0])

N = 25
funs = [fibonacci_closed, fibonacci_for, fibonacci_memoised, fibonacci_recursive,
        fibonacci_recurse_sum, fibonacci_rounding, fibonacci_tail]
for f in funs:
    print "%s:\n     Fib(%s) = %s\n     Time: %.3f s\n     Function Calls: %s\n" % f(N)