From: Logan Capaldo <logancapaldo@...>
Date: 2007-07-14T22:50:22+09:00
Subject: Re: [OT] tail-recursion

------=_Part_27449_3428127.1184421018964
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On 7/14/07, Morton Goldberg <m_goldberg@ameritech.net> wrote:
>
> On Jul 14, 2007, at 1:36 AM, Trevor Squires wrote:
>
> > sum([H|T]) -> H + sum(T);
> > sum([]) -> 0.
> >
> > "Oh my god!  Won't that blow the stack?" - well, I *think* it's
> > okay because of something called 'tail-recursion' - but like you, I
> > don't know what I don't know.


unfortunately this is not a tail recursive call. The recursive call (sum) is
not the last call, + is. To write this tail recursively, you'd want to use
an accumulating parameter:

sum(X) -> asum(0, X).

asum(N, [H|T]) -> asum(H + N, T);
asum(N, []) -> N.


For what it's worth: the function definition is "tail-recursive" and
> the technique used by the compiler/interpreter to prevent stack
> overflow is called "tail-recursion elimination". That is, the
> compiler/interpreter transforms the recursion into an iteration
> (which is relatively easy to do for tail-recursive functions).
>
> Regards, Morton
>
>
>
>

------=_Part_27449_3428127.1184421018964--