;; кэш для функции Аккермана 
(defvar *akk-cache* nil) 
 
;; счетчик рекурсивных вызовов (должен быть обнулен перед вызовом функции akk или akk-cache) 
(defvar *akk-recursive-calls-counter* 0) 
 
 
(defun print-akk-cache () 
  (print *akk-cache*)) 
 
(defun print-akk-calls-counter () 
  (format t "~a~%" *akk-recursive-calls-counter*)) 
 
 
;; эта функция инициализирует кэш указанным размером 
(defun init-akk-cache (m n) 
  (setf *akk-cache* nil) 
  (setf *akk-cache* (make-list m)) 
  (let ((cache-row (make-list n :initial-element 0))) 
    (dotimes (i m) 
      (setf (nth i *akk-cache*) (copy-list cache-row)))) 
  (return-from init-akk-cache t)) 
 
 
;; установка значения в кэше 
(defun set-akk-cache-value (m n value) 
  (setf (nth n (nth m *akk-cache*)) value) 
  (return-from set-akk-cache-value t)) 
 
 
;; получение значения из кэша                
(defun get-akk-cache-value (m n) 
  (if (or (> m (length *akk-cache*)) (> n (length (nth 0 *akk-cache*)))) 
      (format t "FUCK!~%")) 
  (let ((result (nth n (nth m *akk-cache*)))) 
    (return-from get-akk-cache-value result))) 
 
 
;; функция Аккермана без использования кэширования 
(defun akk (m n) 
  (incf *akk-recursive-calls-counter*) 
  (cond ((= m 0) (+ n 1)) 
   ((= n 0) (akk (- m 1) 1)) 
   (t (akk (- m 1) (akk m (- n 1)))))) 
 
 
;; функция Аккермана с использованием кэширования 
(defun akk-cache (m n) 
  (incf *akk-recursive-calls-counter*) 
  (if (/= (get-akk-cache-value m n) 0) 
      (return-from akk-cache (get-akk-cache-value m n)) 
      (let ((value (cond ((= m 0) (+ n 1)) 
          ((= n 0) (akk-cache (- m 1) 1)) 
          (t (akk-cache (- m 1) (akk-cache m (- n 1))))))) 
   (set-akk-cache-value m n value) 
   (return-from akk-cache value)))) 
 
;; 
(defun akk-with-calls-counting () 
  (loop for m from 0 to 3 do 
       (loop for n from 0 to 14 do 
       (setf *akk-recursive-calls-counter* 0) 
       (format t "(~2a ~2a) ~12a [~a]~%" m n (akk m n) *akk-recursive-calls-counter*)))) 
 
(defun akk-cache-with-calls-counting () 
  (loop for m from 0 to 3 do 
       (loop for n from 0 to 14 do 
       (setf *akk-recursive-calls-counter* 0) 
       (format t "(~2a ~2a) ~12a [~a]~%" m n (akk-cache m n) *akk-recursive-calls-counter*)))) 

 
(init-akk-cache 10 1000000) 
(akk-cache-with-calls-counting)