Tco - 把尾调用的递归转化成循环，来解决递归过深时的问题

Emacs-general
1

看了 defun-tco 之后发现写成 Tail call 的递归转化成循环可真是容易，试了下，速度没有提升，但是解决了递归过深时 max-lisp-eval-depth 的问题。

(defun sum (n init)
  (if (= n 0)
      init
    (sum (- n 1) (+ n init))))

(defun-tco sum-tco (n init)
  (if (= n 0)
      init
    (sum-tco (- n 1) (+ n init))))


(benchmark-run 10000 (sum 100 0))
     => (1.9151880000000001 8 1.363888999999972)
(benchmark-run 10000 (sum-tco 100 0))
     => (2.9346200000000002 12 2.045106999999973)

(benchmark-run 1000 (sum 1000 0))
error--> Lisp nesting exceeds `max-lisp-eval-depth'
(benchmark-run 1000 (sum-tco 1000 0))
     => (2.8758369999999998 12 2.0061310000000105)
4 个赞
2

P.S. Scheme强制支持并使用TCO。

3

感觉还应该写个 flet-tco，Tail call 的递归经常要 local function binding

(defun sum (n)
  (flet ((aux (n acc)
              (if (zerop n)
                  acc
                (aux (1- n) (* n acc)))))
    (aux n 0)))

(sum 1000)
error--> Variable binding depth exceeds max-specpdl-size