# [erlang-questions] Modeling Recursion into Tail Recursion

Fred Hebert < >
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()
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+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, )]]
[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], )
map(F, , [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