La récursivité et le mauvais exemple de Fibonacci

Quasiment toute personne ayant suivi un cours sur la récursivité a eu un problème du style : coder la suite de Fibonacci en récursif et en itératif.

Mais partout où j'ai vu une implémentation récursive je suis tombé sur un algorithme non efficace. Pour rappel voici ce qu'on peut trouver.

long long fib(unsigned int n)
{
  if (n == 0)
    return n;
  int a = 0, b = 1, tmp;
  while (--n)
  {
    tmp = a + b;
    a = b;
    b = tmp;
  }
  return b;
}

long long fib_r(unsigned int n)
{
  if (0 == n || 1 == n)
    return n;
  return fib_r(n-1) + fib_r(n-2);
}

Sauf que cet algorithme récursif est pourri, il recalcule sans cesse fib-1 et fib-2 et fait monter la pile là où l'algorithme itératif additionne une variable.
Pour avoir un algorithme récursif équivalent à l'itératif il faut garder le même comportement, c'est à dire garder a et b.

long long fib_r_impl(unsigned int n, long long r, long long rp)
{
  if (0 == n)
    return r;
  return fib_r_impl(n-1, r+rp, r);
}

long long fib_r(unsigned int n)
{
  return fib_r_impl(n,0,1);
}

Cet algo est strictement identique au premier car applique la récursion terminale. Ainsi le code généré par un compilateur (avec les flags d'optimisations) donnera un binaire identique (ou très proche). D'autres langages comme OCaml ou java-script optimise la pile quand il y a une récursion terminale.