In[1]:= AbsoluteTiming[
 f[0] = 1;
 f[1] = 1;
 f[n_] := f[n] = If[OddQ[n], f[(n - 1)/2], f[n/2] + f[n/2 - 1]];
 f[10^25]]

Out[1]= {0.0000377904, 178653872807}