Fibonacci is a fast growing sequence that can easily overflow your integer variables. Fortunately, Python doesn’t have this problem, since it can handle huge integer numbers.
-
#!/usr/bin/env python
-
def fib(n):
-
if n==0 or n==1:
-
ret = n
-
else:
-
ret = fib(n-1) + fib(n-2)
-
return ret
-
-
for i in range(1000):
-
print fib(i)
The example avobe has a big performance issue, due to the recursive calls to calculate n-1 and n-2 values, which are calculated multiple times over and over. By storing the results on a list we solve this issue, although we now relay on the amount of available memory.
-
#!/usr/bin/env python
-
fibs = []
-
def fib(n):
-
if n==0 or n==1:
-
ret = n
-
elif n < len(fibs):
-
ret = fibs[n]
-
else:
-
ret = fib(n-1) + fib(n-2)
-
fibs.append(ret)
-
return ret
-
-
for i in range(1000):
-
print fib(i)
Thus, Fib(1000) = 43,466,557,686,937,456,435,688,527,675,040,625,802,
564,660,517,371,780,402,481,729,089,536,555,417,949,051,890,403,879,840,079,
255,169,295,922,593,080,322,634,775,209,689,623,239,873,322,471,161,642,996,
440,906,533,187,938,298,969,649,928,516,003,704,476,137,795,166,849,228,875