Last active
March 2, 2016 00:18
-
-
Save bahaddinyasar/c84e268c844226d23b82 to your computer and use it in GitHub Desktop.
Fibonacci Implementations in python (iterative, recursive, memoized recursive)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
def fibonacci_iterative(n): | |
if n == 0: | |
return 0 | |
x = 0 | |
y = 1 | |
for i in range(1, n): | |
z = (x + y) | |
(x, y) = (y, z) | |
return z | |
def fibonacci_recursive(n): | |
return n if n < 2 else fib(n-2) + fib(n-1) | |
def memoize(f): | |
cache = {} | |
def decorated_function(*args): | |
if args in cache: | |
return cache[args] | |
else: | |
cache[args] = f(*args) | |
return cache[args] | |
return decorated_function | |
@memoize | |
def fibonacci_memoized(n): | |
return n if n < 2 else fib(n-2) + fib(n-1) | |
# dynamic programming solution | |
def fib(n): | |
fibValues = [0, 1] | |
for i in range(2, n+1): | |
fibValues.append(fibValues[i-1] + fibValues[i-2]) | |
return fibValues[n] |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment