StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>V2 uses standard <strong>accumulating variable</strong> to get tail recursion done:</p> <pre><code>loop ([0;1;2;3;4;5;6;7;8], []) -> loop ([3;4;5;6;7;8], [(0,1,2)]) -> loop ([6;7;8], [(3,4,5), (0,1,2)]) -> loop ([], [(6,7,8), (3,4,5), (0,1,2)]) -> [(6,7,8), (3,4,5), (0,1,2)] </code></pre> <p>V3 uses <a href="http://en.wikipedia.org/wiki/Continuation_passing_style" rel="noreferrer">continuation</a>, or in plain English, an <strong>accumulating function</strong>:</p> <pre><code>loop ([0;1;2;3;4;5;6;7;8], x->x) -> loop ([3;4;5;6;7;8], x->(0;1;2)::x) -> loop ([6;7;8], x->(3;4;5)::x) -> loop ([], x->(6,7,8)::x) -> [(6,7,8)] // x->(6,7,8)::x applies to [] -> [(3,4,5);(6,7,8)] // x->(3,4,5)::x applies to [(6,7,8)] -> [(0,1,2);(3,4,5);(6,7,8)] // x->(0,1,2)::x applies to [(3,4,5);(6,7,8)] </code></pre> <p>You can see the difference between accumulating variables and accumulating functions:</p> <p>Using accumulating variables stops at the last call as the accumulating variable stores the answer. However, the accumulating function still does some <strong>backtrack</strong> work after the last call. It should be noticed that using accumulating functions is indeed tail recursive as the recursive call <code>loop t (fun ls -> accfun ((a,b,c)::ls))</code> is actually the <strong>last</strong> statement of this function. </p> <p>Btw, the code you provided is a good example to show the concept tail recursive functions. One way to understand these sample code is to <strong>work on small cases</strong> as I did in the above two illustrations. After working on some small cases, you will understand the concept deeper. </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