Databases
StackOverflow2013
Postsdbo
POWhat's a good way to rewrite this non-tail-recursive function?
Body
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POWhat's a good way to rewrite this non-tail-recursive function?
    text
    copied!<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>
 

Querying!

 
Guidance
An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload