What's a good way to rewrite this non-tail-recursive function?

Question

For some reason, I am having trouble thinking of a good way to rewrite this function so it uses constant stack space. Most online discussions of tree recursion cheat by using the Fibonacci function and exploiting the properties of that particular problem. Does anyone have any ideas for this "real-world" (well, more real-world than the Fibonacci series) use of recursion?

Clojure is an interesting case since it does not have tail-call optimization, but only tail recursion via the "recur" special form. It also strongly discourages the use of mutable state. It does have many lazy constructs including tree-seq, but I am not able to see how they can help me for this case. Can anyone share some techniques they have picked up from C, Scheme, Haskell, or other programming languages?

(defn flatten [x]
  (let [type (:type x)]
    (cond (or (= type :NIL) (= type :TEXT))
          x
          (= type :CONCAT)
          (doc-concat (flatten (:doc1 x))
                      (flatten (:doc2 x)))
          (= type :NEST)
          (doc-nest (:level x)
                    (flatten (:doc x)))
          (= type :LINE)
          (doc-text " ")
          (= type :UNION)
          (recur (:doc1 x)))))

edit: By request in the comments...

Restated in general terms and using Scheme -- how do I rewrite the following recursion pattern so it doesn't consume stack space or require tail-call optimization of non-self-calls?

(define (frob x)
  (cond ((foo? x)
         x)
        ((bar? x)
         (macerate (f x) (frob (g x))))
        ((thud? x)
         (frobnicate (frob (g x))
                     (frob (h x))))))

I chose annoying names to drive home the point that I am looking for answers that don't rely on the algebraic properties of x, macerate, frobnicate, f, g, or h. I just want to rewrite the recursion.

UPDATE:

Rich Hickey has kindly added an explicit trampoline function to Clojure.

Answer 1

Please don't downvote this because it's ugly. I know it's ugly. But it's a way to do it in trampoline-style (no system stack overflow), and without using gotos.

push x,1 on homemade stack
while stack length > 1
  n = pop
  if (n==1)
    x = pop
    if (type(x)==NIL || type(x)==TEXT)
      push x // this is the "return value"
    else if (type(x)==CONCAT)
      push 2 // say call doc-concat
      push doc2(x), 1 // 2nd recursion
      push doc1(x), 1 // 1st recursion
    else if (type(x)==NEST)
      push 3 // say call doc-nest
      push level(x) // push level argument to doc-nest
      push doc(x), 1 // schedule recursion
    else if (type(x)==LINE)
      push " " // return a blank
    else if (type(x)==UNION)
      push doc1(x), 1 // just recur
  else if (n==2)
    push doc-concat(pop, pop) // finish the CONCAT case
  else if (n==3)
    push doc-nest(pop, pop) // finish the NEST case
  endif
endwhile
// final value is the only value on the stack