Recursive Factorial Function in Common-Lisp

Question

Ok, I'm been learning COMMON LISP programming and I'm working on a very simple program to calculate a factorial of a given integer. Simple, right?

Here's the code so far:

(write-line "Please enter a number...")  
(setq x  (read))
(defun factorial(n)
    (if (= n 1)
            (setq a 1)
    )
    (if (> n 1)
        (setq a (* n (factorial (- n 1))))
    )
    (format t "~D! is ~D" n a)
)

(factorial x)

Problem is, when I run this on either CodeChef or Rexter.com, I get a similar error: "NIL is NOT a number."

I've tried using cond instead of an if to no avail.

As a side note, and most bewildering of all, I've seen a lot of places write the code like this:

   (defun fact(n)
(if (= n 1)
    1
    (* n (fact (- n 1)))))

Which doesn't even make sense to me, what with the 1 just floating out there with no parentheses around it. However, with a little tinkering (writing additional lines outside the function) I can get it to execute (equally bewildering!).

But that's not what I want! I'd like the factorial function to print/return the values without having to execute additional code outside it.

What am I doing wrong?

Answer 1

You can split it up into parts, something like this:

(defun prompt (prompt-str)
  (write-line prompt-str *query-io*)
  (finish-output)
  (read *query-io*))

(defun factorial (n)
  (cond ((= n 1) 1)
        (t (* n
              (factorial (decf n)))))

(defun factorial-driver ()
  (let* ((n (prompt "Enter a number: "))
         (result (factorial n)))
    (format *query-io* "The factorial of ~A is ~A~%" n result)))

And then run the whole thing as (factorial-driver).

Sample interaction:

CL-USER 54 > (factorial-driver)
Enter a number: 
4
The factorial of 4 is 24

Answer 2

One actually needs to flush the I/O buffers in portable code with FINISH-OUTPUT - otherwise the Lisp may want to read something and the prompt hasn't yet been printed. You better replace SETQ with LET, as SETQ does not introduce a variable, it just sets it.

(defun factorial (n)
  (if (= n 1)              
      1                           
      (* n (factorial (- n 1))))) 

(write-line "Please enter a number...")
(finish-output)              ; this makes sure the text is printed now
(let ((x (read)))
 (format t "~D! is ~D" x (factorial x)))

Answer 3

Common Lisp is designed to be compiled. Therefore if you want global or local variables you need to define them before you set them.

On line 2 you give x a value but have not declared the existence of a variable by that name. You can do so as (defvar x), although the name x is considered unidiomatic. Many implementations will give a warning and automatically create a global variable when you try to set something which hasn’t been defined.

In your factorial function you try to set a. This is a treated either as an error or a global variable. Note that in your recursive call you are changing the value of a, although this wouldn’t actually have too much of an effect of the rest of your function were right. Your function is also not reentrant and there is no reason for this. You can introduce a local variable using let. Alternatively you could add it to your lambda list as (n &aux a). Secondarily your factorial function does not return a useful value as format does not return a useful value. In Common Lisp in an (implicit) progn, the value of the final expression is returned. You could fix this by adding a in the line below your format.

For tracing execution you could do (trace factorial) to have proper tracing information automatically printed. Then you could get rid of your format statement.

Finally it is worth noting that the whole function is quite unidiomatic. Your syntax is not normal. Common Lisp implementations come with a pretty printer. Emacs does too (bound to M-q). One does not normally do lots of reading and setting of global variables (except occasionally at the repl). Lisp isn’t really used for scripts in this style and has much better mechanisms for controlling scope. Secondarily one wouldn’t normally use so much mutating of state in a function like this. Here is a different way of doing factorial:

(defun factorial (n)
  (if (< n 2)
      1
      (* n (factorial (1- n)))))

And tail recursively:

(defun factorial (n &optional (a 1))
  (if (< n 2) a (factorial (1- n) (* a n))))

And iteratively (with printing):

(defun factorial (n)
   (loop for i from 1 to n
         with a = 1
         do (setf a (* a i))
            (format t “~a! = ~a~%” i a)
         finally (return a)))

Answer 4

Before answering your question, I would like to tell you some basic things about Lisp. (Neat fix to your solution at the end)

• In Lisp, the output of every function is the "last line executed in the function". Unless you use some syntax manipulation like "return" or "return-from", which is not the Lisp-way.

• The (format t "your string") will always return 'NIL as its output. But before returning the output, this function "prints" the string as well. But the output of format function is 'NIL.

Now, the issue with your code is the output of your function. Again, the output would be the last line which in your case is:

(format t "~D! is ~D" n a)

This will return 'NIL.

To convince yourself, run the following as per your defined function:

(equal (factorial 1) 'nil)

This returns:

1! is 1
T

So it "prints" your string and then outputs T. Hence the output of your function is indeed 'NIL.

So when you input any number greater than 1, the recursive call runs and reaches the end as input 1 and returns 'NIL. and then tries to execute this:

(setq a (* n (factorial (- n 1))))

Where the second argument to * is 'NIL and hence the error.

A quick fix to your solution is to add the last line as the output:

(write-line "Please enter a number...")  
(setq x  (read))
(defun factorial(n)
    (if (= n 1)
            (setq a 1)
    )
    (if (> n 1)
        (setq a (* n (factorial (- n 1))))
    )
    (format t "~D! is ~D" n a)
    a  ;; Now this is the last line, so this will work
)

(factorial x)

Neater code (with Lisp-like indentation)

(defun factorial (n)
  (if (= n 1)              
      1                           
      (* n (factorial (- n 1))))) 

(write-line "Please enter a number...")  
(setq x  (read))
(format t "~D! is ~D" x (factorial x))