fibonacci ***Time limit exceeded***

[frequency]

def fib(number): 
  if number==0: 
      return 0
  elif number==1: 
      return 1
  else: 
    return fib(number-1)+fib(number-2)

n=int(input())
while n!="END" and n>0:
  print (fib(n))
  n=int(input())

With this code i can show the N fibonacci number given. But my code is not accepted because of this
***Time limit exceeded***. Any ideas?

[ichabod801]

You are making the same calculations over and over again. Say you try fib(5). That's fib(4) + fib(3). But those are fib(3) + fib(2) + fib(2) + fib(1). So far you've called fib(3) and fib(2) twice each. It would be faster to just generate the numbers until you have n of them. Now, if you have to pass multiple tests, I would save the numbers you calculate for the first test, so you don't have to calculate them again.

[frequency]

This is the list that they told me,to suppose that i have
F=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...]

[Gribouillis]

Ichabod801's suggestion is an example of dynamic programming. It is probably what you're supposed to do. Accessing F[k] is much faster than calling fib(k). See this image extracted from wikipedia.

[ichabod801]

This is the list that they told me,to suppose that i have
F=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...]

Right. So start with [1, 1], and keep adding the last two numbers together until you have n of them. Then return the last one.

[frequency]

So should i make a look to append the 1 last and 2 last number calculation on the last position,so i can call the item after?

[ichabod801]

I'm not sure I understood your question, but you would start with [1, 1]. Add the last two and append it, to get [1, 1, 2]. Add the last two and append it, to get [1, 1, 2, 3]. Keep going until you have n numbers, and return the last one.

[frequency]

So i made this

f=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
for i in range (99999):
    f.append(f[-1]+f[-2])
user_input=input()
while user_input!="END":
    user_input=int(user_input)
    print (f[user_input-1])
    user_input=input()

9999 in range because it will test maximum 9999 digit number.On idle it works but on my submittion page,it will cause a MemoryError.

[ichabod801]

First of all, you are still doing too much calculation. You only need to calculate until you have as many numbers as requested.

Second of all, you have 5 nines in your range, not 4. If that doesn't fix the problem, just keep track of the last two numbers, and the count of which number you're on.

[frequency]

f=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
for i in range (9999):
    f.append(f[-1]+f[-2])
user_input=input()
while user_input!="END":
    user_input=int(user_input)
    print (f[user_input-1])
    user_input=input()

I actually removed the wrongfuly placed 9 there. Got it working