[erlang-questions] Modeling Recursion into Tail Recursion
Fred Hebert
mononcqc@REDACTED
Sat Mar 14 18:42:50 CET 2015
On 03/14, Harit Himanshu wrote:
> 1. Since the concept for tail recursion is new to me I specially wanted
> to ask that how could I model my thinking to turn recursive functions into
> tail-recursive functions?
A tail-recursive function often does so by taking the call stack, and
turning it into an argument.
The simplest example for this is a function like `sum', defined
recursively as:
sum([]) -> 0;
sum([H|T]) -> H + sum(T).
To make it tail-recursive, observe how it would expand, say with
[1,2,3]:
sum([1,2,3])
1 + sum([2,3])
1 + 2 + sum([3])
1 + 2 + 3 + sum([])
1 + 2 + 3 + 0
6
To turn it tail recursive, let's take all of these 'waiting' additions
and move them as an argument:
sum(List) -> sum(List, 0).
sum([], Sum) -> Sum;
sum([H|T], Sum) -> sum(T, H + Sum).
You will still find all the same information in either. The difference
is that instead of implictly storing your additions in the call stack
(1 + <other computation>), you calculate it at every level and reduce it
slowly:
sum([1,2,3])
sum([1,2,3], 0)
sum([2,3], 1) % 1+0
sum([3], 3) % 3+1 <=> 3+1+0
sum([], 6) % 3+3 <=> 3+3+1+0
6
The same computation takes place, but we moved it implictly. It's even
more obvious with a 'map' function:
map(_, []) -> [];
map(F, [H|T]) -> [F(H) | map(F, T)].
Which expands as:
F = fun(X) -> 2*X end
map(F, [1,2,3])
[2 | map(F, [2,3])]
[2 | [4 | map(F, [3])]]
[2 | [4 | [6 | map(F, [])]]]
[2 | [4 | [6 | []]]]
[2,4,6]
Compared to the tail recursive:
map(F, List) -> map(F, List, []).
map(_, [], Acc) -> lists:reverse(Acc);
map(F, [H|T], Acc) -> map(F, T, [f(H)|Acc]).
Expanding to:
F = fun(X) -> 2*X end
map(F, [1,2,3])
map(F, [1,3,3], [])
map(F, [2,3], [2])
map(F, [3], [4,2])
map(F, [], [6,4,2])
lists:reverse([6,4,2])
[2,4,6]
You can see the stack growing and the list getting smaller in the
recursive function. You can see the same happening with the
tail-recursive function. The reverse step is optional (you could use
[A]++Tail, but it's less efficient), but the interesting part is really
that you take the implicit stack and make it explicit.
> 2. Can we turn every recursive function into tail-recursive? If no, how
> to identify?
I believe you can. I don't have proper enough chops in computer science
to assert so or present a formal proof, but generally, any recursive
function can be made iterative (work in a while loop), and pretty much
all while loops are easy to convert into a tail-recursive functions.
I'll let anyone with proper computer science knowledge or memory answer
this one for me, but really, a good question to ask is 'should you?'
I assert that you shouldn't convert all functions to tail recursive
ones. For example, tree traversal is expressed extremely simply with
recursion. Take the tree:
A
/ \
B C
/ \
D E
The following function:
traverse({leaf, L}) -> show(L);
traverse({tree, Value, Left, Right}) ->
show(Value), traverse(Left), traverse(Right).
will display nodes of the tree in the order A -> B -> D -> E -> C.
Change it for:
traverse({leaf, L}) -> show(L);
traverse({tree, Value, Left, Right}) ->
traverse(Left), show(Value), traverse(Right).
And you get D -> B -> E -> A -> C. Change it for:
traverse({leaf, L}) -> show(L);
traverse({tree, Value, Left, Right}) ->
traverse(Left), traverse(Right), show(Value).
And now you have D -> E -> B -> C -> A.
Expressing these traversals tail-recursively is much harder. But it's
what you need to do if you want to print A -> B -> C -> D -> E
(level-order):
traverse(Tree) -> traverse1([Tree]).
traverse1([]) -> done;
traverse1([{leaf, L} | T]) -> show(L), traverse1(T);
traverse1([{node,V,L,R} | T]) ->
show(V),
traverse1(T++[L,R]).
So now we need to take the upcoming recursions, put them in a queue, and
traverse them iteratively, because digging through the tree is more
trouble. This can be done with *all* traversals, but really, if you can
avoid them, maybe you should.
In cases like 'map', it's often more efficient to write the function
recursively than tail-recursively (you save a reversal, which is a whole
traversal, but garbage-collection can be tricky! See
http://ferd.ca/erlang-s-tail-recursion-is-not-a-silver-bullet.html)
> 3. Any other valuable recommendation based on your learnings?
>
Practice a lot. You may have ease starting to think of your
tail-recursive functions as while loops:
duplicate(N, Term) -> % this is not real code
while N > 0 ->
List = [Term|List],
N = N-1
end,
List.
Which is equivalent to:
duplicate(N, Term) ->
duplicate(N, Term, []).
duplicate(0, _, List) -> List;
duplicate(N, Term, List) when N > 0 ->
duplicate(N-1, Term, [Term|List]).
See the 'N-1' is there in both, the 'N > 0' also (though it can be
implicit), and same for [Term|List], and the final, 'List' to be
returned.
Of course the same is there:
duplicate(0,_) ->
[];
duplicate(N,Term) when N > 0 ->
[Term|duplicate(N-1,Term)].
Eventually, you'll stop thinking in terms of 'while loops' to be
translated in functions, to the opposite: think in functions to be
exploded into while loops.
Regards,
Fred.
More information about the erlang-questions
mailing list