Question

(1) Write a simple Lisp function factorial1 to computee factorial number of n recursivaly (where n is an int >= 0).

(2) Write a Lisp function factorial2 to computee factorial number of n (where n is an int >=0) recursivaly with a global variable (e.g., a list, an array, or a hash tble) to save the result to be used later (memorization) to compute next factorial number. Run the program with test case.

For your test run, the following cases: factorial of 0, 1, 10, 100, 1000, 10000, 100000.

3) Write a Lisp function factorial3 to computee factorial of n (where n is an int >= 0) with a loop (iteratively) with a global variable (e.g., a list, an array, or a hash table, etc.) to save the previous result to be used later. You may use a global variable or hash table or an array to save the results to be used later (memorization) to compute the next factorial number.

Answer 1

Question 1:

;(1) Write a simple Lisp function factorial1 to computee factorial number of n
;recursivaly (where n is an int >= 0).

; defining function factorial1
; parameter: n - integer greater than 0 for
;            for which the factorial should be calculated
; description: calculates the factorial for integer n

(defun factorial1 (n)
  
    ; case for negative answer
   (if (< n 0)
        (return-from factorial1 0)
    )
  
    ;condition for n equal to 0
   (if (= n 0)
        (return-from factorial1 1) ; executed when n equals to 0
        (return-from factorial1 (* n (factorial1 (decf n 1)))) ; executed when n is not equal to 0
                                                               ; i.e. n maybe greater than or lesser to 0
   )
)

(write (factorial1 5))

Output:
120

Question 2:

; (2) Write a Lisp function factorial2 to computee
; factorial number of n (where n is an int >=0) recursivaly
; with a global variable (e.g., a list, an array, or a hash tble)
; to save the result to be used later (memorization) to compute next
; factorial number. Run the program with test case.

; Hash table for storing the factorials
(setq memory (make-hash-table))

; defining function factorial2
; parameter: n - integer greater than 0 for
;            for which the factorial should be calculated
; description: calculates the factorial for integer n

(defun factorial2 (n)

    ; when n is a negative number
    ; return 0
    (if (< n 0)
        (return-from factorial2 0)
    )

    ; when n is equal to 0
    ; return 1
   (if (= n 0)
        (return-from factorial2 1)
   )
  
   ; searching the hash table for the factorial of n
   ; if it is already calculated it will return the factorial
   ; else it will return NIL
    (if (gethash n memory)
        (return-from factorial2 (gethash n memory))
   )
  
   ; recursively calculating the factorial for n
   ; and storing in variable result
   (setq result (* n (factorial2 (- n 1))))
  
    (write "without memory")
    (format t "~C~C" #\return #\linefeed)
  
    ; storing the factorial in Hash map
    (setf (gethash n memory) result)
  
   (return-from factorial2 result)
  
)

(write (factorial2 3))
(format t "~C~C" #\return #\linefeed)
(format t "~C~C" #\return #\linefeed)
(write (factorial2 2))

Output:
"without memory"
"without memory"
"without memory"
6

2

Question 3:

; 3) Write a Lisp function factorial3 to computee
; factorial of n (where n is an int >= 0) with a loop (iteratively)
; with a global variable (e.g., a list, an array, or a hash table, etc.)
; to save the previous result to be used later. You may use a global variable or
; hash table or an array to save the results to be used later (memorization)
; to compute the next factorial number.

; Hash map for storing the factorials
(setq memory (make-hash-table))

; defining function factorial1
; parameter: n - integer greater than 0 for
;            for which the factorial should be calculated
; description: calculates the factorial for integer n

(defun factorial3 (n)

    ; if n is a negative number
    ; return 0
    (if (< n 0)
        (return-from factorial3 0)
    )
  
    ; if n is equal to 0
    ; return 1
    (if (= n 0)
        (return-from factorial3 1)
   )
  
   ; if n is equal to 1
    ; return 1
   (if (= n 1)
        (return-from factorial3 1)
   )
  
   ; declaring a variable result = 0
   (defvar result 1)
  
   ; Loop to calculate factorial
    (loop
        ; going out of the loop when n = 1
        (when (= n 1) (return result))
      
        ; checking if the factorial for n is already calculated
        ; if it is already calculated multiplying the result with the factorial
        ; and going out of the loop
        (if (gethash n memory)
            (return (* result (gethash n memory)))
        )
      
        ; multiplying for factorial
        (setq result (* result n))
      
        ;decrementing n by 1
        (decf n 1)
  
        (write "without memory")
        (format t "~C~C" #\return #\linefeed)
  
        ; saving the factorial value into hash map
        (setf (gethash (+ n 1) memory) result)
    )
  
    (return-from factorial3 result)
  
)

(write (factorial3 5))
(format t "~C~C" #\return #\linefeed)
(format t "~C~C" #\return #\linefeed)
(write (factorial3 6))

Output:

"without memory"
"without memory"
"without memory"
"without memory"
120

"without memory"
720