Ищем пример типичной рекурсии дерева, превращенной в хвостовую рекурсию

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