[3/1/99]

===============================================================================

* Tail recursion - a quick reminder:
  Tail recursion is a way of writing a loop without using a loop - instead,
  recursive syntax is used.  This is something that should be implemented by
  the compiler/interpreter we work with.  It is also a piece of knowledge that
  can actually affect the way we write programs.  Here is an example:

  --------------------
    int n_sum_iter( int n, int a ) {
      if (n == 0)
        return a;
      else
        return n_sum_iter( n-1, a+n );
    }
    int n_sum( int n ) {
      return n_sum_iter( n, 0 );
    }
  --------------------

  That is C syntax for a tail-recursive function (iter), here is the Scheme
  equivalent:

  --------------------
    (define (n-sum-iter n a)
      (if (zero? n)
        a
        (n-sum-iter (- n 1) (+ a n))))
    (define (n-sum n)
      (n-sum-iter n))
  --------------------

  When we write this function, we know that we have a tail-recursion optimizing
  interpreter/compiler, otherwise we wouldn't write this since then the
  function call (integers-sum 100000) will probably explode the stack.
  Note: Some C compiler do support tail recursion.

  Can do some list examples using tail recusion.

===============================================================================

* Note on tail-recursion and running time:

  There are two resources that we usually want to measure: the running time of
  the program, and the space it takes.

  The running time of a function _is not_ affected by the fact that it is tail
  recursive or not - this is just a matter of space needed for its running.
  For example, the two factorial versions that we used have the _same_ running
  time, just different space needs.  The fact that there is less to save on a
  "stack" can, of course, make things run faster, but this is not really our
  problem.

===============================================================================

* Go _quickly_ over this example:
  Tail-recursion can also happen when we have _two_ mutual recursive functions:

  --------------------
    (define (i-even? n f)
      (if (zero? n)
        f
        (i-odd? (- n 1) (not f))))

    (define (i-odd? n f)
      (if (zero? n)
        f
        (i-even? (- n 1) (not f))))

    (define (even? n)
      (i-even? n #t))

    (define (odd? n)
      (i-odd? n #f))
  --------------------

  Here is a sample trace:

  --------------------
    (even? 5)
    (i-even? 5 #t)
    (i-odd? (- 5 1) (not #t))
    (i-odd? 4 #f)
    (i-even? 3 #t)
    (i-odd? 2 #f)
    (i-even? 1 #t)
    (i-odd? 0 #f)
    #f
  --------------------

  And this shows us a tail-recursive behavior - the expression takes a fixed
  amount of space = no information should be saved on stack between function
  calls.

===============================================================================

* Some more complicated list examples, go quickly, not necessary to go over all
  of the examples:

  --------------------
    (member? x l)
  --------------------

  Determines whether x is in l.  Actually, the Scheme primitive is called
  "member" because it is not a "pure" predicate - if c is not in l, you get #f,
  but if it _is_, you get the tail that starts with x.  This means you _can_
  use it as a predicate, but we use "?" for functions that are "pure"
  predicates in the sense that you don't care about the actual value they
  return, but only if it's #f or not.  Actually, if you (define member? member)
  then your actually saying that "member?" is used like that.  (This is not
  actually needed).

  Implementation is easy.

  --------------------
    (reverse l)
  --------------------

  returns a list which has the same elements of l, but in reverse order.  This
  could be defined as:

  --------------------
    (define (reverse l)
      (if (null? l)
        l
        (append (reverse (tail l)) (list (head l)))))
  --------------------

  but this has bad running time, O(n^2).  Here, using a tail recursion version
  helps with running time (this is _not_ always the case, more later):

  --------------------
    (define (reverse l)
      (define (iter l a)
        (if (null? l)
          a
          (iter (tail l) (cons (head l) a))))
      (iter l empty))
  --------------------

  Another useful function that is simpler to see by its definition than to
  describe in English:

  --------------------
    (define (map f l)
      (if (null? l)
        l
        (cons (f (head l)) (map f (tail l)))))
  --------------------

  We can try making this tail-recursive:

  --------------------
    (define (map f l)
      (define (iter l a)
        (if (null? l)
          (reverse a)
          (iter (tail l) (cons (f (head l)) a))))
      (iter l empty))
  --------------------

  The result _is_ tail recursive, but it didn't help much - not in run-time and
  not in memory.  [Actually memory is 1/2 of the previous version and runtime
  is twice, but in O notation it is the same.]

  Note that the built-in map function works on more than one input list, for a
  function that gets more than one argument, for example:

  --------------------
    (map + (list 1 2 3) (list 4 5 6) (list 7 8 9))
      --> (12 15 18)
  --------------------

  Another cute and useful function:

  --------------------
    (define (filter pred? l)
      (cond ((null? l) l)
            ((pred? (head l)) (cons (head l) (filter pred? (tail l))))
            (else (filter pred? (tail l)))))
  --------------------

===============================================================================