scheme - 可以简化此功能(制作更多 "fast")吗？

Question

我想知道这是否是该函数最快的版本。

(defun foo (x y)
  (cond 
   ;if x = 0, return y+1
   ((zp x) (+ 1 y)) 
   ;if y = 0, return foo on decrement x and 1
   ((zp y) (foo (- x 1) 1)) 
   ;else run foo on decrement x and y = (foo x (- y 1))
   (t (foo (- x 1) (foo x (- y 1)))))) 

当我运行它时，我通常会遇到堆栈溢出错误，所以我想找出一种方法来计算类似 (foo 3 1000000) 的东西而不使用计算机。

通过分析函数，我认为它是将 foo 嵌入到导致 (foo 3 1000000) 溢出的递归情况中。但是既然你在递减 y，那么步数是否正好等于 y？

编辑:删除评论中的谎言

Answer 1

12 年前我写了这篇文章:

(defun ackermann (m n)
  (declare (fixnum m n) (optimize (speed 3) (safety 0)))
  (let ((memo (make-hash-table :test #'equal))
        (ncal 0) (nhit 0))
    (labels ((ack (aa bb)
               (incf ncal)
               (cond ((zerop aa) (1+ bb))
                     ((= 1 aa) (+ 2 bb))
                     ((= 2 aa) (+ 3 (* 2 bb)))
                     ((= 3 aa) (- (ash 1 (+ 3 bb)) 3))
                     ((let* ((key (cons aa bb))
                             (val (gethash key memo)))
                        (cond (val (incf nhit) val)
                              (t (setq val (if (zerop bb)
                                               (ack (1- aa) 1)
                                               (ack (1- aa) (ack aa (1- bb)))))
                                 (setf (gethash key memo) val)
                                 val)))))))
      (let ((ret (ack m n)))
        (format t "A(~d,~d)=~:d (~:d calls, ~:d cache hits)~%"
                m n ret ncal nhit)
        (values ret memo)))))

如您所见，我对较小的 a 使用了显式公式，对较大的 a 使用了内存。

但是请注意，此函数增长如此之快以致于尝试计算实际值毫无意义；你将更快地耗尽宇宙中的原子——无论是否内存。