Skip to content

Instantly share code, notes, and snippets.

@ikkebr

ikkebr/fib.py

Created October 2, 2011 03:23
Show Gist options
  • Save ikkebr/1256985 to your computer and use it in GitHub Desktop.
Save ikkebr/1256985 to your computer and use it in GitHub Desktop.
Download ZIP
Simple Recursive Fibonacci
Raw
fib.py
fibs = {0: 0, 1: 1}
def fib(n):
if n in fibs: return fibs[n]
if n % 2 == 0:
fibs[n] = ((2 * fib((n / 2) - 1)) + fib(n / 2)) * fib(n / 2)
else:
fibs[n] = (fib((n - 1) / 2) ** 2) + (fib((n + 1) / 2) ** 2)
return fibs[n]
fib(10000000)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment