[erlang-questions] Modeling Recursion into Tail Recursion
e@REDACTED
e@REDACTED
Tue Mar 24 18:34:24 CET 2015
i think this question deserves a cheat-sheet for all times.
something like: a quick overview of all sorts of recursion
so, i am going to contribute a bit:
>>> As for the second question I'm not 100% sure I'm remembering this
>>> correctly but using continuation-passing-style you could express every
>>> recursive function with tail-recursion.
>>
>> Yes you can but it's not USEFUL to do so.
>>
>> There are plenty of good reasons to do this, such as situations
>> where a function needs more than one continuation, or you want to
>> simulate long-distance return, or you want a function that can
>> return more than once, e.g., to do backtracking.
(1) continuation should not necessarily be represented as a whole
function call, a subset of arguments might suffice.
(2) i think that a good illustration for CPS is the tree-traversing.
you can easily traverse tree in one order (following the edges of the
tree at each recursive call), in this case each call will be complete
upon traversing a respective sub-tree entirely.
Which is not the only reasonable traversing order -- one might want to
traverse "siblings-first".
So, If you want to traverse through siblings before you go deeper in the
tree, then CPS is the solution.
regarding tail recursion:
(3) it is not always useful.
for example, your function projects a scalar to a list,
foo: Int -> [Int]
then the entire list will appear on the stack either way, with or
without tail recursion.
stack consumption of the "foo" is O(N) -- it is easier not to bother
with tail recursion.
More information about the erlang-questions
mailing list