尋找一個典型的樹狀遞歸變成尾遞歸的例子

Question

任何像拼合，計數原子等嵌套列表將會很好。

順便說一句，我對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))))))