Hello, I have been trying to find a way to run faster some recursive functions, and I started by coding Fibonacci. Apart from using memoization and the default definition

f[0] = 0;
f[1] = 1;
f[x_]:=f[x] = f[x-1] + f[x-2];

i also used a faster method, using linear algebra and tables ( I believe method is known more or less, no real need to mention it, but if someone is interested let me know).

fib[x_] := m[x][[1, 2]]
m[n_] := MatrixPower[{{1, 1}, {1, 0}}, n];
fib[200000] // AbsoluteTiming

Nevertheless searching the internet I came across the following method, that is really impressive. Unfortunately I cannot understand the logic inside module.

fib2[0] = 0;
fib2[n_] := Module[{f},

  f[n, p1_, _] := p1;
  f[x_, p1_, p2_] := f[x + 1, p1 + p2, p1];
  f[1, 1, 0]
  ]


Block[{$IterationLimit = Infinity}, fib2[200000]] // AbsoluteTiming

I can tell that fib2 receives an initial value equal to 0 for n=0. Then inside module, a new function is defined, where it has 3 variables, and for the requested n (from fib2) and for any p2 value, function f returns p1 always. Then the problem of understanding lies with second line f[x_, p1_, p2_] := f[x + 1, p1 + p2, p1]; and finally the 3rd line is something like giving initial values for n=1 <=> fib2=1 (i think). Could someone please explain it to me analytically? And furthermore, if I rewrite it

Module[{f},
       f[1, 1, 0];
      f[n, p1_, _] := p1;
      f[x_, p1_, p2_] := f[x + 1, p1 + p2, p1];
      ]

it does not return anything, why so? Why does f[1,1,0] have to be entered at the last line (of module). Thank you

ps: the need for $IterationLimit is pretty clear, no need to elaborate there