# Tail-recursion

**URL:** <https://www.ruby-forum.com/t/tail-recursion/109397>\
**Category:** Ruby\
**Created:** [July 14, 2007, 8:16am UTC](https://www.ruby-forum.com/t/tail-recursion/109397 "2007-07-14T08:16:34Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![Morton\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/dfb087/32.png) [@Morton\_G](https://www.ruby-forum.com/u/Morton_G)\
**Post date:** [July 14, 2007, 8:16am UTC](https://www.ruby-forum.com/t/tail-recursion/109397/1 "2007-07-14T08:16:34Z")

</div>

On Jul 14, 2007, at 1:36 AM, Trevor S. 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.

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

---

<div class="post-metadata">

**Author:** ![Morton\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/dfb087/32.png) [@Morton\_G](https://www.ruby-forum.com/u/Morton_G)\
**Post date:** [July 14, 2007, 3:51pm UTC](https://www.ruby-forum.com/t/tail-recursion/109397/2 "2007-07-14T15:51:04Z")

</div>

On 7/14/07, Morton G. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote:

> On Jul 14, 2007, at 1:36 AM, Trevor S. 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

---

<div class="post-metadata">

**Author:** ![Morton\_G](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/m/dfb087/32.png) [@Morton\_G](https://www.ruby-forum.com/u/Morton_G)\
**Post date:** [July 14, 2007, 10:50pm UTC](https://www.ruby-forum.com/t/tail-recursion/109397/3 "2007-07-14T22:50:31Z")

</div>

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