## Fibonacci

int fib (int n)
{ return (n == 0 || n == 1) ? 1 : fib(n-2) + fib(n-1); }

Not only is this algorithm not tail recursive, but it wastes time
recomputing the same values over and over (fib(n-1) requires
recomputing fib(n-3) and fib(n-2), both of which had already been
computed by fib(n-2)).
It is possible to do much better by using a *bottom-up*
algorithm instead of a *top-down* algorithm.

int fib_aux (int n,int i,int j)
{ return (n == 0) ? i : fib_aux(n-1,i+j,i); }
int fib (int n)
{ return fib_aux(n,1,0); }

Notice that:
fib(n) = fib_aux(n,1,0) = fib_aux(n-k,fib(k),fib(k-1))

The interesting argument is the second one. When the first
argument reaches 0, n=k and the second argument is the desired value
fib(n).