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
···
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.
> 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
···
On 7/14/07, Morton Goldberg <m_goldberg@ameritech.net> wrote:
On Jul 14, 2007, at 1:36 AM, Trevor Squires wrote:
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
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