[erlang-questions] Modeling Recursion into Tail Recursion

[Fred Hebert]

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.