scheme - 寻找一个典型的树递归变成尾递归形式的例子

Question

嵌套列表上的任何类似 flatten、count-atoms 等的东西都可以。

顺便说一句，我对 CPS 转换或“对树”不感兴趣。

Answer 1

您可以只编写一个带有堆栈的循环，该堆栈记录要处理的下一棵树。你还需要一个蓄能器。但这与 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))))))