Now that we are equipped with all the tools for developing LISP programs, let
us venture into something more interesting. Consider the definition of
factorials:
A D V E R T I S E M E N T
n! = 1
if n = 1
n! = n * (n - 1)!
if n > 1
We can implement a function to compute factorials using recursion:
(defun factorial (N)
"Compute the factorial of N."
(if (= N 1)
1
(* N (factorial (- N 1)))))
The if form checks if N is one, and returns one if that is the
case, or else returns N * (N - 1)!. Several points are worth noting:
The condition expression (= N 1) is a relational expression. It
returns boolean values T or NIL. In fact, LISP treats
NIL as false, and everything else as true. Other relational operators
include the following:
Relational Operators
Meaning
(= xy)
x is equal to y
(/= xy)
x is not equal to y
(< xy)
x is less than y
(> xy)
x is greater than y
(<= xy)
x is no greater than y
(>= xy)
x is no less than y
The if form is not a strict function (strict functions
evaluate their arguments in applicative order). Instead, the if
form evaluates the condition (= N 1) before further evaluating the
other two arguments. If the condition evaluates to true, then only the
second argument is evaluated, and its value is returned as the value of the
if form. Otherwise, the third argument is evaluated, and its value
is returned. Forms that are not strict functions are called special
forms.
The function is recursive. The definition of factorial involves
invocation of itself. Recursion is, for now, our only mechanism for
producing looping behavior. Specifically, the kind of recursion we are
looking at is called linear recursion, in which the function may
make at most one recursive call from any level of invocation.
To better understand the last point, we can make use of the debugging
facility trace (do not compile your code if you want to use trace):
USER(11): (trace factorial)
(FACTORIAL)
USER(12): (factorial 4)
0: (FACTORIAL 4)
1: (FACTORIAL 3)
2: (FACTORIAL 2)
3: (FACTORIAL 1)
3: returned 1
2: returned 2
1: returned 6
0: returned 24
24
Tracing factorial allows us to examine the recursive invocation of the
function. As you can see, at most one recursive call is made from each level of
invocation.
