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?