Obvious recursive solution may be inherently inefficient. E.g.
Fibonacci:
<UL>
  <LI>Obvious recursive algorithm is <EM>exponential</EM>: 2**n
      additions to compute fibonacci(n).<P>
  <LI>Yet there exists a simple <EM>linear</EM> time, <EM>constant</EM>
      space algorithm.
</UL>

<P><IMG SRC="/icons/danger.gif">
Therefore, it is essential, after we have solved the problem, to
critically examine our solution and attempt to improve on it; both by
removing sources of inefficiency and by refining its elegance.
<P>

<P><B>Tail Recursion:</B>
is a critical notion. A tail recursive algorithm executes in constant
space and can be highly optimized by the compiler. We now take a brief
look at it.