The <CODE>fibonacci</CODE> function (2 base cases, 2 recursive calls):
<PRE>
fibonacci(0) = 1
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-2) + fibonacci(n-1) [for n&gt;1]</PRE>
Let's compute <CODE>fibonacci(4)</CODE>:
<PRE>
fibonacci(4)
=  fibonacci(3)                  + fibonacci(2)
= (fibonacci(2)  + fibonacci(1)) + (fibonacci(1) + fibonacci(0))
= ((fibonacci(1) + fibonacci(0)) + 1) + (1 + 1)
= (     1        +      1      ) + 1) + (1 + 1)
= 5</PRE>

<H2>Computing Examples</H2>

<P><B>Structural definition of a Stack:</B>
<UL>
  <LI>A stack is either EMPTY
  <LI>or it consists of 2 parts: a `top' value and a `remainder' which
      is a stack
</UL>
For example S = (7,(29,(11,EMPTY)))

<P>Recursive definitions are extremely common in Computer Science
(e.g. Lists, Trees, etc).