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).