当前位置：文江博客话题详情

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

发布于 2024-08-30 08:43:33 字数 65 浏览 2 评论 0原文

嵌套列表上的诸如展平、计数原子等任何东西都可以。

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

隐诗 2024-09-06 08:43:33

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

You can just write a loop with a stack that records the next trees to process. You also need an accumulator. But this isn't all that different from CPS so it may not be what you're looking for.

(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))))))

回复收藏 0 原文

~没有更多了~