fibonacci ***Time limit exceeded***

[nilamo]

So normally, for generating infinite sequences, you'd use a generator:

>>> def find_fibs():
...   last_two = (1, 1)
...   yield 1
...   yield 1
...   while True:
...     new_num = sum(last_two)
...     yield new_num
...     last_two = (last_two[1], new_num)
...
>>> fibs = find_fibs()
>>> for _ in range(10):
...   print(next(fibs))
...
1
1
2
3
5
8
13
21
34
55

But, as ichabod801 mentioned, if the point is that you'll be finding similar numbers repeatedly, you want to keep track of what the old numbers were, and only calculate new numbers if needed. Similar to this:

>>> def fibs(num, results=[1, 1]):
...   while num > len(results):
...     print("**generating new fib**")
...     results.append(results[-1] + results[-2])
...   return results[:num]
...
>>> fibs(2)
[1, 1]
>>> fibs(5)
**generating new fib**
**generating new fib**
**generating new fib**
[1, 1, 2, 3, 5]
>>> fibs(3)
[1, 1, 2]
>>> fibs(10)
**generating new fib**
**generating new fib**
**generating new fib**
**generating new fib**
**generating new fib**
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
>>> fibs(6)
[1, 1, 2, 3, 5, 8]

The difference being a memory issue. If you want to generate the 500 millionth fibonacci number, the generator will give you what that number is, while keeping track of what every previous number is might use up all your memory before giving an answer, which would throw an error instead of getting a result.