Recursion
      
      
Functional languages like Haskell don't have variables and commands because it can introduce sharing bugs. For example, if one function unwittingly modifies a global variable, other functions that share the global variable may stop working.

Without iterative commands (while/for/do-while) how do functional languages iterate? The answer is recursion.

The general format of a recusive function is:

   f 0 = baseCase
   f n = combine n f(n - 1)
      where
         combine count oldResult = newResult

For example, assume

   bricks n = # of bricks needed to build a height n staircase
   
Here's what a staircase of height 3 looks like:

       []
     [][]
   [][][]
   
So

   bricks 3 = 6
   
Clearly no bricks are needed to construct a height 0 staircase, so:

> bricks 0 = 0 -- base case

Notice that we can build a staircase of height n by first building a staiercase of height n - 1 and then gluing a column of n bricks onto the right edge:

              []            []
     []   +   []  =       [][]
   [][]       []        [][][]
   
Therefore:

> bricks n = combine n (bricks(n - 1))
>      where 
>         combine count oldResult = count + oldResult

After writing a recursive function it's a good idea to trace a few calls to the function. This will help you debug the function and it will help you to understand how the recursion works. A trace is a list of intermediate expressions that must be evaluated when we call the function. Usually it is sufficient just to show the important intermediate expressions. A trace in which all intermediate expressions are shown is called a computation.

For example:

   bricks 3
   = 3 + bricks 2
   = 3 + 2 + bricks 1
   = 3 + 2 + 1 + bricks 0
   = 3 + 2 + 1 + 0
   = 3 + 2 + 1
   = 3 + 3
   = 6
   
The length of a computation is proportional to the CPU usage. Clearly this is proportional to n in the example above. We write:

   cpu usage = O(n)
   
The width of the computation is the number of tokens appearing in the largest expression. This is proportional to the memory usage. In the example above this is also proportional to n. We write:

   memory usage = O(n)
   
In Java we could have used iteration to implement this function:

   class BrickCalculator {
      static int bricks(int n) {
         int result = 0;
         for(int i = 1; i <= n; i++)
            result += i;
         return result;
      }
   }
   
Clearly:

   cpu usage = O(n)
   memory usage = O(1)
   
Realizing that iteration uses less memory than recursion, most functional programming languages optimize tail recursive functions. A function is tail recursive if there is no work to be done after the recusrive call. Notice that this isn't the case in traditional recusrion as the result of the recursive call still needs to be combined with the count.

The format of a tail recursion is:

   f n = iter n baseCase
      where
         iter 0 result = result
         iter count result = iter (count - 1) (combine count result)
         combine count oldResult = newResult
         
Here is the tail recursive version of bricks:

> bricks2 n = iter n 0
>      where
>         iter 0 result = result
>         iter count result = iter (count - 1) (combine count result)
>         combine count oldResult = count + oldResult

Let's trace a call:

   bricks2 3
   = iter 3 0
   = iter 2 3
   = iter 1 5
   = iter 0 6
   = 6
   
Notice that:

   cpu usage = O(n)
   memory usage = O(1)
   
In some cases a recursive function can be turned into a non-recursive, non-iterative function. This is analogous to solving a differential equation. For example, the equation:

   state(t) = 2 * state'(t) + 100
   
Says that the state of a system at time t is proportional to the rate of change in the state at time t. We can solve this:

   state(t) = e^[2t + ln(100)]
   
Observe that:

   bricks n 
      = n + (n - 1) + (n - 2) + ... + 3 + 2 + 1 
      = (n + 1) + (n - 1 + 2) + (n - 2 + 3) + ...
      = (n + 1) * n/2
      
Thus:

> bricks3 n = ((n + 1) * n) `div` 2

Notice that:

   cpu usage = O(1)
   memory usage = O(1)