From: Trevor Squires <trevor@...>
Date: 2007-07-15T05:41:20+09:00
Subject: Re: [OT] tail-recursion

Hey Logan and Morton,

my thanks to both of you for the information.  Quite a lot has fallen  
into place in my head because of these two emails.

Trev

On 14-Jul-07, at 6:50 AM, Logan Capaldo wrote:

> 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
>>
>>
>>
>>