Python Forum

Here's how I would have done it:

f=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
while True:
    user_input = input()
    if user_input == 'END':
        break
    user_input = int(user_input)
    while len(f) < user_input:
        f.append(sum(f[-2:])
    print (f[user_input - 1])

That only calculates what you need when you need it.

Your code has an error at the last print,i will check it further as soon as i go home

---

optimized the code a bit for my standards

f=[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89]
user_input = input()
while user_input !='END':
    user_input = int(user_input)
    while type(user_input)==int:
        while len(f) < user_input:
          f.append(sum(f[-2:]))
        print (f[user_input - 1])
        user_input=input()

Your code will throw an exception on line 4 when they enter 'END'.

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.

(Nov-24-2018, 02:49 AM)frequency Wrote: [ -> ]

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

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?

It seems to me that you can't have Fibonacci without recursive solution (at least in school / university) :-). This is somehow considered 'appropriate' way of learning recursion. Recursion can be helpful but it's memory hungry and it's not very well suited for Python. However, if you absolutely must use recursion and the number is not very large (so that Python recursion depth is not reached) you can take advantage of memoization and fit nicely into time limit.

import time
start_time = time.time()

def fibonacci(n, d):
    """
    Calculate n-th Fibonacci number using recursion with memoization.
    """
    
    if n in d:
        return d[n]
    
    else:
        stacked = fibonacci(n - 1, d) + fibonacci(n-2, d)
        d[n] = stacked
        return stacked
    
d = {1: 1, 2: 1}
print(fibonacci(2967, d))   # max value

print(f'time: {time.time() - start_time} seconds')

5210070734289118676556659504172397216509110684811035423298698167608113070
8128298569412879157715400318322090085906471884461561425531080766704209506
4311080110751154013406591832134966583308143574796700315698273930037147293
5213339912864755255418769562822777951268745753053628637531122736216232998
2608605087960788184953369249606869764593142447603256366652678730040462508
2678511875453604344284964368071643450341691576353630336917618689891862786
8101774706249610049853926508865933137189372424857166415874230698017498326
2019706158006070552174196824071976060605681771809636978040161730581446676
084619548504486422369069065085516578

time: 0.005608797073364258 seconds

You don't need recursion for Fibonacci numbers

>>> def fib(n):
...     if n == 0:
...         return 0
...     a, b = 0, 1
...     for i in range(n-1):
...         a, b = b, a + b
...     return b
... 
>>> fib(2967)
5210070734289118...

I think Fibonacci numbers is a terrible example because one finds it in many many language tutorials and it is useless and it doesn't teach you anything. Good examples are

• The towers of Hanoi for recursion.
  
• The edit distance for dynamic programming.
  

(Nov-28-2018, 09:43 AM)Gribouillis Wrote: [ -> ]You don't need recursion for Fibonacci numbers. I think Fibonacci numbers is a terrible example /../

I agree with you totally.

Still it's reality of life that lot (majority?) of students have submit calculation of fibonacci numbers using recursion in order to pass the term.

Quote:Still it's reality of life that lot (majority?) of students have submit calculation of fibonacci numbers using recursion

The actual lesson of the Fibonacci example is that recursion can be the worst idea on a problem. That's what need to be taught.

Thank you for your time.i really apreciate your efford! I tweaked it a bit to make it fully functional

def fib(n):
  if n == 0:
    return 0
  a, b = 0, 1
  for i in range(n-1):
    a, b = b, a + b
  return b

user_input=input()
while user_input!="END":
  user_input=int(user_input)
  print (fib(user_input))
  user_input=input()