This definition can be directly translated to the following LISP code:
(defun fibonacci (N)
"Compute the N'th Fibonacci number."
(if (or (zerop N) (= N 1))
1
(+ (fibonacci (- N 1)) (fibonacci (- N 2)))))
Again, several observations can be made. First, the function call (zerop
N) tests if N is zero. It is merely a shorthand for (= N 0).
As such, zerop returns either T or NIL. We call such
a boolean function a predicate, as indicated by the suffix p.
Some other built-in shorthands and predicates are the following:
Shorthand
Meaning
(1+ x)
(+ x 1)
(1- x)
(- x 1)
(zerop x)
(= x 0)
(plusp x)
(> x 0)
(minusp x)
(< x 0)
(evenp x)
(= (rem x 2) 0)
(oddp x)
(/= (rem x 2) 0)
Second, the or form is a logical operator. Like if, or
is not a strict function. It evaluates its arguments from left to right,
returning non-NIL immediately if it encounters an argument that
evaluates to non-NIL. It evaluates to NIL if all tests fail.
For example, in the expression (or t (= 1 1)), the second argument
(= 1 1) will not be evaluated. Similar logical connectives are listed
below:
Logical Operators
Meaning
(or x1x2 ... xn)
Logical or
(and x1x2 ... xn)
Logical and
(not x)
Logical negation
Third, the function definition contains two self references. It first
recursively evaluates (fibonacci (- N 1)) to compute Fib(N-1),
then evaluates (fibonacci (- N 2)) to obtain Fib(N-2), and
lastly return their sum. This kind of recursive definitiion is called double
recursion (more generally, multiple recursion). Tracing the
function yields the following:
USER(20): (fibonacci 3)
0: (FIBONACCI 3)
1: (FIBONACCI 2)
2: (FIBONACCI 1)
2: returned 1
2: (FIBONACCI 0)
2: returned 1
1: returned 2
1: (FIBONACCI 1)
1: returned 1
0: returned 3
3
