Looking for an example of a typical tree-recursion turned into a tail-recursive form.

Question

Anything like flatten, count-atoms, etc. over nested lists would do fine.

BTW, I'm not interested in a CPS transformation or "pairs-trees".

Answer 1

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