.comment -*- Mode:TEXT; -*-
.comment shows them how to write FIB and FACT and talks about recursion
.comment and scope of variable bindings.
.document FIB - Examples of how to write two simple recursive Lisp functions.
.tag FIB
Lesson FIB, Version 2                    Revised by Victoria Pigman, 9/1/82

This lesson is designed to give you an introduction to writing actual 
programs in Lisp. The first example we shall use is the Fibonacci 
function. Later we shall play with Factorial. Aren't we lucky!


--- FIBONACCI ---

Just as a reminder as to what the Fibonacci function is, (which I shall 
call FIB from here on...) let me give the definition:

     FIB (0) = 1
     FIB (1) = 1 
     FIB (N) = FIB (N-1) + FIB (N-2)

This type of definition is called RECURSIVE, becuase FIB is defined in 
terms of previous values of FIB until it gets to a value it knows (1 or 0).

We have defined for you a function FIB which will do this in a similar manner.

.eval-print
(DEFUN FIB (N)
  (COND ((= N 0) 1)
	((= N 1) 1)
	(T (+ (FIB (1- N))
	      (FIB (- N 2))))))

[Note: The function = returns T if its arguments are equal (they must be
	integer numbers) and NIL otherwise. The function 1- returns one less 
	than its argument. (1- n) could have been written (- n 1)]


Play with this for a while to convince yourself it does what it claims. If 
you have difficulty, try it out in pieces. That is, pick an n for yourself
and decide whether:
     (= n 0)
is true, and if so, say 1. If you've decided that was false, then decide about
     (= n 1) 
and again say 1 if it returns T. Otherwise, start on
     (fib (1- n))
etc. until it becomes clear. In other words, play computer and follow through
the algorithm.
.try

Note that the function doesn't get confused when you call it from itself. In 
languages like FORTRAN this would not be the case (in FORTRAN it would even get
confused trying to return and would loop endlessly). The reason it doesn't get 
confused is that every atom on the bound variable list gets a new value that
merely OBSCURES the old one; it doesn't destroy the old one. The new value goes
away when the function is exited. In other words, the SCOPE of the value is 
just inside the call to the function. So, if you say (FIB 0) after FIB returns 
1, N will have the same value it had before (FIB 0) was called. If it had been 
previously undefined, it will still be undefined.


--- FACTORIAL ---

Now let's play with FACTORIAL. (Let's call it FACT for short.) To remind you
of what factorial does, here's its definition:

     FACT (0) is 1
     FACT (1) is 1
     FACT (N) is N*FACT (N-1)

Since you've seen how we go from the definition of FIB to the actual program, 
it's your turn to try on factorial.

Please don't continue until you think you have got it, as I will give the 
solution in the next section.
.try

Did it look something like this?
.pp
(DEFUN FACT (N)
  (COND ((= N 0) 1)		; necessary for the case n=0...
	((= N 1) 1)		; is this one necessary at all? 
	(T (* N (FACT (-1 N))))))


Note that it is possible for one function to call another, and indeed all 
large programs are written like this. This is the basis behind structured 
programming, i.e. you write a program and wherever you need to do something 
complicated, you just say (PERFORM-HAIRY-OPERATION-ON <ARGUMENTS>) and then 
when you are done, you write a function PERFORM-HAIRY-OPERATION-ON which is
simpler than writing the whole big problem, and the hard parts you just call 
a function to do and write that function later. You don't write the smaller 
functions until you know exactly what they have to do, and you can call them 
in your definitions of the larger operation just like they were pre-defined
functions. But don't forget to write them before you are done! The system will
complain about functions which are not defined when you actually try to use the
function.
 
OK, that's the end of this lesson. There will be more of them soon, and we
will get into some more ways of writing programs and just how to handle more 
complicated objects and problems. 
.next MEMQ