fibonacci ***Time limit exceeded***

[Gribouillis]

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.