# Ruby tail recursion

**URL:** <https://rubytalk.org/t/ruby-tail-recursion/23338>\
**Category:** ruby-talk\
**Created:** [16 December 2005 03:41 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338 "2005-12-16T03:41:06Z")\
**Posts on this page:** 19\
**Page:** 1

<div class="post-metadata">

**Author:** ![Mark4](https://avatars.discourse-cdn.com/v4/letter/m/77aa72/32.png) [@Mark4](https://rubytalk.org/u/Mark4)\
**Post date:** [16 December 2005 03:41 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/1 "2005-12-16T03:41:06Z")

</div>

In another thread someone mentioned tail recursion doesn't work right  
in Ruby. Could someone please expand upon that?

---

<div class="post-metadata">

**Author:** ![Anonymous\_Coward](https://avatars.discourse-cdn.com/v4/letter/a/94ad74/32.png) [@Anonymous\_Coward](https://rubytalk.org/u/Anonymous_Coward)\
**Post date:** [16 December 2005 03:55 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/2 "2005-12-16T03:55:33Z")

</div>

The current interpreter does not do tail-recursion optimization.  
This means that deeply recursive operations are not as efficient  
as they could be.

E

> **···**
>
> On 2005.12.16 12:41, Mark Ericson \<mark.ericson@gmail.com\> wrote:
> 
> > In another thread someone mentioned tail recursion doesn't work right  
> > in Ruby. Could someone please expand upon that?

---

<div class="post-metadata">

**Author:** ![Johannes\_Friestad](https://avatars.discourse-cdn.com/v4/letter/j/9fc29f/32.png) [@Johannes\_Friestad](https://rubytalk.org/u/Johannes_Friestad)\
**Post date:** [16 December 2005 08:22 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/3 "2005-12-16T08:22:43Z")

</div>

Here's a somewhat lengthy explanation. Well, you asked for it 🙂

Here's a recursive method:

def tailrec\_max(arr, i=0, best=-Infinity)  
&nbsp;&nbsp;return best if i==arr.length  
&nbsp;&nbsp;rec\_max(arr, i+1, (arr[i]\>best ? arr[i] : best))  
end

Assuming we call tailrec\_max([1,2,3,4]), the stack will at some point  
look like this:  
- tairec\_max([..], 4, 4) # i==arr.length, returns best=4  
- tairec\_max([..], 3, 3)  
- tairec\_max([..], 2, 2)  
- tairec\_max([..], 1, 1)  
- tairec\_max([..], 0, -Infinity) # initial call  
The method calls itself a number of times, and each invocation is  
pushed on the stack. The callers stay on the stack, each waiting for  
the return of the method it called.

This is standard method invocation, and happens every time a method  
calls another. The calls further down the stack are waiting for the  
calls above to complete before continuing whatever they were doing.

But in some cases there is no point for a method to hang around..  
The tailrec\_max method is such a case: After it has called itself,  
there is nothing more for it to do, except to wait for the return  
value and pass it on unchanged. This is called tail recursion.

Some languages optimize for this: When the compiler or interpreter can  
determine that the return value of the method is the same as the  
return value of the next method call, it can in effect skip the  
recursive calls and recompile the entire method into a for loop, which  
is faster and does not run into stack size limitations no matter how  
many recursive calls there are.

Here's a similar method that cannot be optimized:

def non\_tailrec(arr, i=0, best=-Infinity)  
&nbsp;&nbsp;return best if i==arr.length  
&nbsp;&nbsp;rec\_max(arr, i+1, (arr[i]\>best ? arr[i] : best))+1  
end

The '+1' at the end means that this method needs the stack: It has to  
wait for the return value in order to do the add.

Lisp does tail recursion optimization (in most implementations  
anyway), Ruby doesn't.

It's not a matter of "not working right": Recursion, tail or no tail,  
works just as well as any other method call in Ruby. Plenty of  
languages thrive without optimizing for tail recursion, Java is one of  
them.

The combination of a small stack and lack of tail recursion  
optimization does mean that in Ruby, recursion can hardly replace  
every other looping construct the way it can in Lisp. You'll be the  
judge of whether that is important.

I think Lisp is a somewhat special case: The entire language grew out  
of a recursive definition (called lambda calculus), and a Lisp dialect  
I used at university had no 'for', no 'while' and no other data  
structure than linked lists. Now in a language like that, it makes  
sense to optimize for recursion 😉

jf

> **···**
>
> > On 2005.12.16 12:41, Mark Ericson \<mark.ericson@gmail.com\> wrote:  
> > \> In another thread someone mentioned tail recursion doesn't work right  
> > \> in Ruby. Could someone please expand upon that?

---

<div class="post-metadata">

**Author:** ![Collins\_Justin](https://avatars.discourse-cdn.com/v4/letter/c/e19adc/32.png) [@Collins\_Justin](https://rubytalk.org/u/Collins_Justin)\
**Post date:** [16 December 2005 09:38 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/4 "2005-12-16T09:38:24Z")

</div>

I wouldn't really call it optimization (although I guess it is), it's more like implementing them in such a way that you get around the limitations of computer memory. (As opposed to just making them run faster or something.) It doesn't really have anything to do with efficiency in that sense.

Code like:

def fun(x)  
&nbsp;&nbsp;&nbsp;&nbsp;fun(x)  
end

fun(10)

should run forever, like it would in a language like Scheme or Lua. A function calls itself, which calls itself, for infinitly. Unfortunately, Ruby does not currently work that way.

It's not that Ruby doesn't work "right" in this case, it just runs into the limits of hardware (the size of the stack). The "proper" way of implementing tail calls would never use the stack, so it wouldn't be an issue.

By the way, is there a particular reason why tail calls aren't implemented that way?

-Justin

> **···**
>
> -----Original Message-----  
> From: ruerue@purr.magical-cat.org on behalf of Eero Saynatkari  
> Sent: Thu 12/15/2005 7:55 PM  
> To: ruby-talk ML  
> Subject: Re: Ruby tail recursion
> 
> -----BEGIN PGP SIGNED MESSAGE-----  
> Hash: SHA1
> 
> On 2005.12.16 12:41, Mark Ericson \<mark.ericson@gmail.com\> wrote:
> 
> > In another thread someone mentioned tail recursion doesn't work right  
> > in Ruby. Could someone please expand upon that?
> 
> The current interpreter does not do tail-recursion optimization.  
> This means that deeply recursive operations are not as efficient  
> as they could be.
> 
> E

---

<div class="post-metadata">

**Author:** ![jwesley](https://avatars.discourse-cdn.com/v4/letter/j/74df32/32.png) [@jwesley](https://rubytalk.org/u/jwesley)\
**Post date:** [18 December 2005 14:57 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/5 "2005-12-18T14:57:46Z")

</div>

The reason that tail recursion is "important" is that functional  
programming style generally avoids using iterators (or more generally  
it avoids changing any variable after it's initialized).

So instead of a "loop", one would use recursion. So most "functional"  
programming languages require any implementation of that language to  
properly handle tail-recursion. With this "optimization" one can  
freely implement an algorithm in the "functional" style w/o concerns of  
it bombing out when the input is too large.

I found that ~1300 is the maximum depth of the stack on my machine....  
So I can't use recursion to iterate over more than ~1300 items.

---

<div class="post-metadata">

**Author:** ![Johannes\_Friestad](https://avatars.discourse-cdn.com/v4/letter/j/9fc29f/32.png) [@Johannes\_Friestad](https://rubytalk.org/u/Johannes_Friestad)\
**Post date:** [16 December 2005 08:40 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/6 "2005-12-16T08:40:01Z")

</div>

Code corrections:

def tailrec\_max(arr, i=0, best=-Infinity)  
return best if i==arr.length  
tailrec\_max(arr, i+1, (arr[i]\>best ? arr[i] : best))  
end

def non\_tailrec(arr, i=0, best=-Infinity)  
return best if i==arr.length  
non\_tailrec(arr, i+1, (arr[i]\>best ? arr[i] : best))+1  
end

---

<div class="post-metadata">

**Author:** ![Mark4](https://avatars.discourse-cdn.com/v4/letter/m/77aa72/32.png) [@Mark4](https://rubytalk.org/u/Mark4)\
**Post date:** [16 December 2005 20:40 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/7 "2005-12-16T20:40:49Z")

</div>

Thanks, I get it now! Some languages will generate code that won't  
overflow the stack when doing tail recursion. Ruby doesn't have that  
optimization, yet.

> **···**
>
> On 12/16/05, Collins, Justin \<collinsj@seattleu.edu\> wrote:
> 
> > I wouldn't really call it optimization (although I guess it is), it's more like implementing them in such a way that you get around the limitations of computer memory. (As opposed to just making them run faster or something.) It doesn't really have anything to do with efficiency in that sense.
> > 
> > Code like:
> > 
> > def fun(x)  
> > &nbsp;&nbsp;&nbsp;&nbsp;fun(x)  
> > end
> > 
> > fun(10)
> > 
> > should run forever, like it would in a language like Scheme or Lua. A function calls itself, which calls itself, for infinitly. Unfortunately, Ruby does not currently work that way.
> > 
> > It's not that Ruby doesn't work "right" in this case, it just runs into the limits of hardware (the size of the stack). The "proper" way of implementing tail calls would never use the stack, so it wouldn't be an issue.
> > 
> > By the way, is there a particular reason why tail calls aren't implemented that way?

---

<div class="post-metadata">

**Author:** ![Eero\_Saynatkari1](https://avatars.discourse-cdn.com/v4/letter/e/46a35a/32.png) [@Eero\_Saynatkari1](https://rubytalk.org/u/Eero_Saynatkari1)\
**Post date:** [16 December 2005 20:42 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/8 "2005-12-16T20:42:55Z")

</div>

Collins, Justin wrote:

> I wouldn't really call it optimization (although I guess it is), it's  
> more like implementing them in such a way that you get around the  
> limitations of computer memory. (As opposed to just making them run  
> faster or something.) It doesn't really have anything to do with  
> efficiency in that sense.

I really only call it 'tail-recursion optimization'  
(or TRO) because that is its common name in the  
literature.

> Code like:
> 
> def fun(x)  
> &nbsp;&nbsp;&nbsp;&nbsp;fun(x)  
> end
> 
> fun(10)
> 
> should run forever, like it would in a language like Scheme or Lua. A  
> function calls itself, which calls itself, for infinitly. Unfortunately,  
> Ruby does not currently work that way.
> 
> It's not that Ruby doesn't work "right" in this case, it just runs into  
> the limits of hardware (the size of the stack). The "proper" way of  
> implementing tail calls would never use the stack, so it wouldn't be an  
> issue.

Lua also stops running when you pull the power cord 🙂  
There are limitations to all implementations, and the  
'correct' way to do recursion is to actually recurse.  
The TRO modifies code to run more efficiently (in the  
broadest sense) for a special case which is why, I  
presume, it was called an optimization. A non-frame-based  
call system, for example, would not require this.

> By the way, is there a particular reason why tail calls aren't  
> implemented that way?

It is much harder to implement correctly 🙂

> -Justin

E

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Johannes\_Friestad](https://avatars.discourse-cdn.com/v4/letter/j/9fc29f/32.png) [@Johannes\_Friestad](https://rubytalk.org/u/Johannes_Friestad)\
**Post date:** [16 December 2005 21:03 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/9 "2005-12-16T21:03:42Z")

</div>

> I wouldn't really call it optimization (although I guess it is), it's more like implementing them in such a way that you get around the limitations of computer memory. (As opposed to just making them run faster or something.) It doesn't really have anything to do with efficiency in that sense.

I agree that it's not (just) optimization in the sense of 'runs  
faster'. Without tail-recursion optimization there are things you  
simply cannot do in a recursive fashion.

A simple example is iterating over a collection.  
For example, these two 'max' methods are equivalent, so which one you  
prefer is mainly a matter of style preferences.

def each\_max(elms)  
&nbsp;&nbsp;max=-Infinity  
&nbsp;&nbsp;elms.each {|x| max=x if x\>max }  
&nbsp;&nbsp;max  
end

def for\_max(elms)  
&nbsp;&nbsp;max=-Infinity  
&nbsp;&nbsp;for elm in elms  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;max=elm if elm\>max  
&nbsp;&nbsp;end  
&nbsp;&nbsp;max  
end

The tail recursive version,

def tailrec\_max(arr, i=0, max=-Infinity)  
&nbsp;&nbsp;return max if i==arr.length  
&nbsp;&nbsp;tailrec\_max(arr, i+1, (arr[i]\>max ? arr[i] : max)  
end

would be equivalent to the first two, and offer a third style, if Ruby  
had tail optimization.  
As it is, each element access adds another method call on the stack,  
and the recursion does not bottom out before the end of the sequence,  
so we will get an exception whenever there are more than 'stack-limit'  
elements in the sequence. The limit is 1200 on my system.  
1200 elements in a sequence is nothing - consider iterating over  
characters in a string, or lines in a log file, it doesn't take much  
to have 1200 characters or lines.  
This makes recursive iteration in Ruby a curiosity that cannot be  
actually used for very much.

> By the way, is there a particular reason why tail calls aren't implemented that way?

My guess is that it's not implemented simply because recursion isn't  
used very much in Ruby. (It's the chicken and egg: Recursion won't be  
generally viable until the optimization is in place.)

Although I can live without it, I'd like to see tail recursion  
optimization in Ruby.  
If it's up to debate, I'm voting yes 🙂

jf

---

<div class="post-metadata">

**Author:** ![Jakub\_Hegenbart1](https://avatars.discourse-cdn.com/v4/letter/j/4af34b/32.png) [@Jakub\_Hegenbart1](https://rubytalk.org/u/Jakub_Hegenbart1)\
**Post date:** [16 December 2005 22:28 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/10 "2005-12-16T22:28:53Z")

</div>

Collins wrote:

> I wouldn't really call it optimization (although I guess it is), it's more like implementing them in such a way that you get around the limitations of computer memory. (As opposed to just making them run faster or something.) It doesn't really have anything to do with efficiency in that sense.  
> &nbsp;&nbsp;

Well, what about this, for example?

[http://big-oh.cs.hamilton.edu/~bailey/pubs/techreps/TR-2001-2.pdf](http://big-oh.cs.hamilton.edu/~bailey/pubs/techreps/TR-2001-2.pdf)

Tail calls are essentialy safe GOTOs with argument passing, there is a potential for performance gain. 😉 But in Ruby, its benefits wouldn't be that noticeable, I guess...I kind of don't think that the programming style that Ruby encourages is a good candidate for tail call optimization. 😃

That doesn't mean that a (fictional) Ruby implementation compiling to native code couldn't take advantage of some tail-call optimizable intermediate form, but the current implementation IMO doesn't need it.

Jakub

---

<div class="post-metadata">

**Author:** ![Gary\_Wright](https://avatars.discourse-cdn.com/v4/letter/g/58956e/32.png) [@Gary\_Wright](https://rubytalk.org/u/Gary_Wright)\
**Post date:** [18 December 2005 17:01 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/11 "2005-12-18T17:01:18Z")

</div>

I hope people do realize that they can change the  
maximum size of the stack allocated to their ruby process. For  
example on Mac OS X using bash:

$ ulimit -s  
8192  
$ ruby -e '@i = 0; def foo; @i += 1; foo; end; begin; foo; rescue; puts @i; end'  
1204  
$ ulimit -s 16384  
$ ruby -e '@i = 0; def foo; @i += 1; foo; end; begin; foo; rescue; puts @i; end'  
2484

The ulimit command is built-in to the shell so if you are looking for  
ways to change the maximum size of the stack for your processes, look  
for ulimit or limit in your shell documentation.

I don't know enough about Windows to offer any hints for that environment.

Gary Wright

`

> **···**
>
> On Dec 18, 2005, at 9:57 AM, jwesley wrote:
> 
> > I found that ~1300 is the maximum depth of the stack on my machine....  
> > So I can't use recursion to iterate over more than ~1300 items.

---

<div class="post-metadata">

**Author:** ![Collins\_Justin](https://avatars.discourse-cdn.com/v4/letter/c/e19adc/32.png) [@Collins\_Justin](https://rubytalk.org/u/Collins_Justin)\
**Post date:** [17 December 2005 05:22 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/12 "2005-12-17T05:22:20Z")

</div>

Yes, you are right - it can improve performance. What I meant was more that performance gains aren't usually the reason for doing it.

However, I am fairly sure it isn't that difficult (in the general case) to implement tail calls this way. For example, in one of my classes we implemented a parser,interpreter,stack,heap,etc. with proper tail calls. Of course, it was for a tiny language, so that's why I'm not sure about how easy it would be to do with Ruby.

The article you linked says at the end:  
"Automatic optimization, on the other hand, is easy to implement in a compiler  
and has little run-time cost. It will always identify opportunities for  
tail recursion removal, even in complex functions. It improves execution  
time without degrading the quality of source code, in some  
cases by more than 700%, and can even beat carefully hand-optimized  
code. Tail recursion removal frees the programmer to program  
in the most elegant and natural style, without worrying about  
performance problems resulting from inefficient language implementations."

Sounds like a good reason to implement it to me!

I do agree that Ruby doesn't encourage programming recursively, really, but why shouldn't it? Recursion isn't necessary, but it can allow for "nicer" solutions to naturally recursive problems.

BTW, I am not going to be upset if this isn't implemented in Ruby, I'm just saying it would nice 🙂

-Justin

> **···**
>
> -----Original Message-----  
> From: Jakub Hegenbart [mailto:kyosuke@seznam.cz]  
> Sent: Fri 12/16/2005 2:28 PM  
> To: ruby-talk ML  
> Subject: Re: Ruby tail recursion
> 
> Collins wrote:
> 
> > I wouldn't really call it optimization (although I guess it is), it's more like implementing them in such a way that you get around the limitations of computer memory. (As opposed to just making them run faster or something.) It doesn't really have anything to do with efficiency in that sense.  
> > &nbsp;&nbsp;
> 
> Well, what about this, for example?
> 
> [http://big-oh.cs.hamilton.edu/~bailey/pubs/techreps/TR-2001-2.pdf](http://big-oh.cs.hamilton.edu/~bailey/pubs/techreps/TR-2001-2.pdf)
> 
> Tail calls are essentialy safe GOTOs with argument passing, there is a  
> potential for performance gain. 😉 But in Ruby, its benefits wouldn't  
> be that noticeable, I guess...I kind of don't think that the programming  
> style that Ruby encourages is a good candidate for tail call  
> optimization. 😃
> 
> That doesn't mean that a (fictional) Ruby implementation compiling to  
> native code couldn't take advantage of some tail-call optimizable  
> intermediate form, but the current implementation IMO doesn't need it.
> 
> Jakub

---

<div class="post-metadata">

**Author:** ![Neil\_Stevens](https://avatars.discourse-cdn.com/v4/letter/n/e9c0ed/32.png) [@Neil\_Stevens](https://rubytalk.org/u/Neil_Stevens)\
**Post date:** [17 December 2005 06:07 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/13 "2005-12-17T06:07:46Z")

</div>

Jakub Hegenbart wrote:

> Tail calls are essentialy safe GOTOs with argument passing, there is a  
> potential for performance gain. 😉 But in Ruby, its benefits wouldn't  
> be that noticeable, I guess...I kind of don't think that the programming  
> style that Ruby encourages is a good candidate for tail call  
> optimization. 😃

Good point. Tail-call recursion is just a form of recursion that's easy  
to turn into iteration, but (at least to me) one of ruby's strengths is  
its iterators, so one might as well just write code in iterative form  
instead of tail-call recursive form!

> **···**
>
> --  
> Neil Stevens - neil@hakubi.us
> 
> 'A republic, if you can keep it.' -- Benjamin Franklin

---

<div class="post-metadata">

**Author:** ![gabriele\_renzi3](https://avatars.discourse-cdn.com/v4/letter/g/7bcc69/32.png) [@gabriele\_renzi3](https://rubytalk.org/u/gabriele_renzi3)\
**Post date:** [18 December 2005 19:37 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/14 "2005-12-18T19:37:46Z")

</div>

gwtmp01@mac.com ha scritto:

> **···**
>
> > On Dec 18, 2005, at 9:57 AM, jwesley wrote:
> > 
> > > I found that ~1300 is the maximum depth of the stack on my machine....  
> > > So I can't use recursion to iterate over more than ~1300 items.
> > 
> > I hope people do realize that they can change the  
> > maximum size of the stack allocated to their ruby process. For  
> > example on Mac OS X using bash:
> 
> \<snip\>
> 
> IIRC ruby 1.9 even has Process.setrlimit as a builtin, not sure about 1.8.4 .

---

<div class="post-metadata">

**Author:** ![Pit](https://avatars.discourse-cdn.com/v4/letter/p/f14d63/32.png) [@Pit](https://rubytalk.org/u/Pit)\
**Post date:** [19 December 2005 20:03 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/15 "2005-12-19T20:03:44Z")

</div>

gwtmp01@mac.com schrieb:

> > I found that ~1300 is the maximum depth of the stack on my machine....  
> > So I can't use recursion to iterate over more than ~1300 items.
> 
> I hope people do realize that they can change the  
> maximum size of the stack allocated to their ruby process. For  
> example on Mac OS X using bash:
> 
> $ ulimit -s  
> 8192  
> $ ruby -e '@i = 0; def foo; @i += 1; foo; end; begin; foo; rescue; puts @i; end'  
> 1204  
> $ ulimit -s 16384  
> $ ruby -e '@i = 0; def foo; @i += 1; foo; end; begin; foo; rescue; puts @i; end'  
> 2484
> 
> The ulimit command is built-in to the shell so if you are looking for  
> ways to change the maximum size of the stack for your processes, look  
> for ulimit or limit in your shell documentation.
> 
> I don't know enough about Windows to offer any hints for that environment.

If you search in the tuby-talk archives, you can find this:

&nbsp;&nbsp;&nbsp;@i = 0  
&nbsp;&nbsp;&nbsp;def foo  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@i += 1  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;foo  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;begin  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;foo  
&nbsp;&nbsp;&nbsp;rescue  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts @i # =\> 1342  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;self.class.tailcall\_optimize :foo

&nbsp;&nbsp;&nbsp;require "timeout"  
&nbsp;&nbsp;&nbsp;begin  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Timeout.timeout 10 do  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;foo  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;rescue Exception =\> e  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;puts @i # =\> 542798  
&nbsp;&nbsp;&nbsp;end

Implemented in Ruby, so not as fast as real TRO.

Regards,  
Pit

> **···**
>
> > On Dec 18, 2005, at 9:57 AM, jwesley wrote:

---

<div class="post-metadata">

**Author:** ![HAL\_9000](https://avatars.discourse-cdn.com/v4/letter/h/90ced4/32.png) [@HAL\_9000](https://rubytalk.org/u/HAL_9000)\
**Post date:** [17 December 2005 06:29 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/16 "2005-12-17T06:29:47Z")

</div>

Neil Stevens wrote:

> Good point. Tail-call recursion is just a form of recursion that's easy  
> to turn into iteration, but (at least to me) one of ruby's strengths is  
> its iterators, so one might as well just write code in iterative form  
> instead of tail-call recursive form!

Well, my take is this. If you happen to write recursive code, and it  
happens to be tail-call optimizable, the interpreter should be smart  
enough not to let the stack grow unnecessarily. That's a fairly easy  
fix if I understand rightly.

That's a separate issue from whether that style is necessarily the  
best in a given situation.

Hal

---

<div class="post-metadata">

**Author:** ![gabriele\_renzi3](https://avatars.discourse-cdn.com/v4/letter/g/7bcc69/32.png) [@gabriele\_renzi3](https://rubytalk.org/u/gabriele_renzi3)\
**Post date:** [17 December 2005 14:22 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/17 "2005-12-17T14:22:47Z")

</div>

Collins, Justin ha scritto:

> Yes, you are right - it can improve performance. What I meant was more that performance gains aren't usually the reason for doing it.
> 
> However, I am fairly sure it isn't that difficult (in the general case) to implement tail

\> calls this way. For example, in one of my classes we implemented a parser,  
\> interpreter,stack,heap,etc. with proper tail calls.  
\> Of course, it was for a tiny language, so that's why I'm not sure  
\> about how easy it would be to do with Ruby.

> The article you linked says at the end:  
> "Automatic optimization, on the other hand, is easy to implement in a compiler  
> and has little run-time cost. It will always identify opportunities for  
> tail recursion removal, even in complex functions. It improves execution  
> time without degrading the quality of source code, in some  
> cases by more than 700%, and can even beat carefully hand-optimized  
> code. Tail recursion removal frees the programmer to program  
> in the most elegant and natural style, without worrying about  
> performance problems resulting from inefficient language implementations."
> 
> Sounds like a good reason to implement it to me!
> 
> I do agree that Ruby doesn't encourage programming recursively, really, but why shouldn't it? Recursion isn't necessary, but it can allow for "nicer" solutions to naturally recursive problems.
> 
> BTW, I am not going to be upset if this isn't implemented in Ruby, I'm just saying it would nice 🙂
> 
> -Justin

I think it is worth noting that Koichi Sasada said once that he plans to support tail call optimization in YARV, even because IIRC he wants it to be able to support Scheme too, which requires TCO.  
I think he'd appreciate if someone could do that (hint! hint!).

---

<div class="post-metadata">

**Author:** ![gabriele\_renzi3](https://avatars.discourse-cdn.com/v4/letter/g/7bcc69/32.png) [@gabriele\_renzi3](https://rubytalk.org/u/gabriele_renzi3)\
**Post date:** [17 December 2005 14:27 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/18 "2005-12-17T14:27:46Z")

</div>

Neil Stevens ha scritto:

> Jakub Hegenbart wrote:
> 
> > Tail calls are essentialy safe GOTOs with argument passing, there is a  
> > potential for performance gain. 😉 But in Ruby, its benefits wouldn't  
> > be that noticeable, I guess...I kind of don't think that the programming  
> > style that Ruby encourages is a good candidate for tail call  
> > optimization. 😃
> 
> Good point. Tail-call recursion is just a form of recursion that's easy  
> to turn into iteration, but (at least to me) one of ruby's strengths is  
> its iterators, so one might as well just write code in iterative form  
> instead of tail-call recursive form!

well, but maybe it could be nice to write iterators in a recursive way, i.e

class Parser  
&nbsp;&nbsp;def each\_token &blk  
&nbsp;&nbsp;&nbsp;tok=shift\_token!  
&nbsp;&nbsp;&nbsp;blk.call(tok)  
&nbsp;&nbsp;&nbsp;each\_token(&blk)  
&nbsp;&nbsp;end  
end

---

<div class="post-metadata">

**Author:** ![Christian\_Neukirche1](https://avatars.discourse-cdn.com/v4/letter/c/ee7513/32.png) [@Christian\_Neukirche1](https://rubytalk.org/u/Christian_Neukirche1)\
**Post date:** [17 December 2005 15:59 UTC](https://rubytalk.org/t/ruby-tail-recursion/23338/19 "2005-12-17T15:59:31Z")

</div>

gabriele renzi \<surrender\_it@-remove-yahoo.it\> writes:

> I think it is worth noting that Koichi Sasada said once that he plans  
> to support tail call optimization in YARV, even because IIRC he wants  
> it to be able to support Scheme too, which requires TCO.  
> I think he'd appreciate if someone could do that (hint! hint!).

IIRC, YARV already supports reusing the current stack frame for calls  
to the same method (that's not real TCO, but far better than nothing).

> **···**
>
> --  
> Christian Neukirchen \<chneukirchen@gmail.com\> [http://chneukirchen.org](http://chneukirchen.org)
