Finding large Fibonacci Number in Python I'm doing Project Euler at 1000-digit Fibonacci number - Problem 25 which says 


  The Fibonacci sequence is defined by the recurrence relation:
  
  Fn = Fn−1 + Fn−2, where F1 = 1 and F2 = 1.
  
  Hence the first 12 terms will be:

F1 = 1
F2 = 1
F3 = 2
F4 = 3
F5 = 5
F6 = 8
F7 = 13
F8 = 21
F9 = 34
F10 = 55
F11 = 89
F12 = 144

  
  The 12th term, F12, is the first term to contain three digits.
  
  What is the index of the first term in the Fibonacci sequence to contain 1000 digits?


I approached this by writing a recursive function in Python that finds the nth Fibonacci number as follows: 

def Fibonacci(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return (Fibonacci(n-1) + Fibonacci(n-2))


However, this function runs very, very slowly. It slows down severely as n approaches 100.

What can I do to make it faster?
Issue
Your issue is you compute fibonacci(i) for one number multiple times.
To understand this, consider computing fibonacci(5). The function would call fibonacci(4) and fibonacci(3) at the end. Now what happens in fibonacci(4)? It would call fibonacci(3) and fibonacci(2). Now you can notice, that the function gets called 2 times for the number 3, which is a serious issue, since that can go VERY deep in the recursion and you can gain a massive overhead because of this.
Solution
Because fibonacci is a pure function, it returns the same value every time it is called with the same parameters. So there's a simple trick you can do to avoid so much time on recalculating what you already found. You can store the result of fibonacci for a specific number in an array, and if it's called again, just return that instead of computing everything again. This trick is called memoization. The Fibonacci sequence is often used as the introductory example for dynamic programming and memoization.
See this nice video explaining the concept of memoization and dynamic programming
Code
This is a simple implementation of memoization for this problem.
cache = {}

def fibonacci(n):
    if n in cache:
        return cache[n]

    if n == 1 or n == 2:
        return 1
    else:
        result = fibonacci(n-1) + fibonacci(n-2)
        cache[n] = result
        return result