[erlang-questions] tail recursion

[Joe Armstrong]

On 5/31/07, Jason Dusek <jsnx@REDACTED> wrote:
> Hi All,
>
> I have a server like this:
>
> server({X, Y}) ->
>   receive
>     {update, NewState} ->
>       server(NewState);
>     {x, Client} ->
>       Client ! X,
>       server({X, Y});
>     {y, Client} ->
>       Client ! Y,
>       server({X, Y});
>   end
>   .
>
> Its tail recursive but, unfortunately, a little redundant -- I'd like
> to rewrite it like this:
>
> server({X, Y}) ->
>   receive
>     {update, NewState} ->
>       server(NewState);
>     {x, Client} ->
>       Client ! X;
>     {y, Client} ->
>       Client ! Y;
>   end,
>   server({X, Y})
>   .
>
> But I worry that the compiler and interpreter will fail to recognize
> my server as tail recursive. Will my rewrite blow the stack?

Yes you will blow the stack  - this is not tail recursive.
I'll explain why, I'll rewrite your code a bit.
suppose we have this:

> server({X, Y}) ->
>   receive
>     {update, NewState} ->
>       foo(NewState);         <--- X (I call foo here instead of server)
>     {x, Client} ->
>       Client ! X;
>     {y, Client} ->
>       Client ! Y;
>   end,
>   server({X, Y})   <--- Y

When foo returns (at point X) we call server (at Y)
So the compiler creates a new stack frame every time foo is called

Now this code *is* tail recursive if foo returns. But in your case
you called server(NewState) *which never returns*

So each pass through the code at point X builds an additional call frame
on the stack - bad news - after a while you'll run out of memory

/Joe