Permalink
Branch: master
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
35 lines (27 sloc) 1.3 KB
#create a method that solves for the nth fibonacci number
#fibonaci number is a sequence where each number is the sum of the previous two
#
from math import floor, sqrt
#solves the problem iteratively, by using the range function to go through each index summing the last two results
def iterative(n):
#this is counter intuitive, but assigning the 0 to last and 1 to second last results in these being flipped
#in the first iteration, which then enables us to move forward methodically from that point.
last, second_last = 0,1
for x in range(n):
last, second_last = last+second_last, last
return last
#solves the problem recursively, by having the function call itself to get and then sum the last two results
#pretty code but nasty performance Fib(N) = (1/sqrt(5)) * 1.618^(N+1)
def recursive(n):
return 1 if (n in (1,2)) else (recursive(n-1) + recursive(n-2))
#solves the problem recursively, but intelligently - it's a meld of recursion and iteration
#slightly harder to read but far more performant - still ultimately limited by the stack
def smart_recursive(n):
def fib(a, b, c):
if c < 1: return a
else: return fib(b, a + b, c - 1)
return fib(0, 1, n)
#solves the problem mathematically, using binet's formula
def binet(n):
phi = (1+5**.5)/2
return int(floor((phi**n)/sqrt(5)+.5))