[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