title: What's a good way to rewrite this non-tail-recursive function?
body: <p>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?</p>
  
  <p><a href="http://clojure.org" rel="noreferrer">Clojure</a> 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 <a href="http://clojure.org/api#toc489" rel="noreferrer">tree-seq</a>, 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?</p>
  
  <pre><code>(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)))))
  </code></pre>
  
  <p>edit: By request in the comments...</p>
  
  <p>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?</p>
  
  <pre><code>(define (frob x)
    (cond ((foo? x)
           x)
          ((bar? x)
           (macerate (f x) (frob (g x))))
          ((thud? x)
           (frobnicate (frob (g x))
                       (frob (h x))))))
  </code></pre>
  
  <p>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.</p>
  
  <p><strong>UPDATE</strong>:</p>
  
  <p>Rich Hickey has kindly added an explicit <a href="http://lambda-the-ultimate.org/node/3106" rel="noreferrer">trampoline function</a> to Clojure.</p>