Recursion

Today I solved this problem using some nice (and easy to find) formulas for computing F[n]:

F[2n] = F[n]*(F[n-1] + F[n+1]) and

F[2n-1] = F^2[n-1] + F^2[n]

with these you cand recursevly compute F[n] fast enough (~0.25 sec). I also precalculated a table with first 2000 Fibonacci and when the recursion dropped below 2000 it returned the computed value.

I see some nice times on the best AC list. Will you please tell us how you did it? What formulas, optimizations...

Thank you