寻找一个典型的树递归转化为尾部递归形式的例子

您可以用一个记录下一个要处理的树的堆栈来编写一个循环。你还需要一个蓄电池。但这和CPS没什么不同,所以它可能不是你想要的。

(define (atom? x) 
  (not (pair? x)))
(define (size tree)
  (let loop ((t tree) (stack '()) (total 0))
    (cond
      ((and (atom? t) (null? stack)) (add1 total))
      ((atom? t) (loop (car stack) (cdr stack) (add1 total)))
      (else (loop (cadr t) (append (cddr t) stack) (add1 total))))))
(define (flatten tree)
  (let loop ((t tree) (stack '()) (l '()))
    (cond
      ((and (atom? t) (null? stack)) (reverse (cons t l)))
      ((atom? t) (loop (car stack) (cdr stack) (cons t l)))
      (else (loop (cadr t) (append (cddr t) stack) (cons (car t) l))))))