# Efficiency of recursion (stack level too deep) **URL:** \ **Category:** Ruby\ **Created:** [November 14, 2007, 4:49am UTC](https://www.ruby-forum.com/t/efficiency-of-recursion-stack-level-too-deep/120146 "2007-11-14T04:49:57Z")\ **Posts on this page:** 4\ **Page:** 1
**Author:** ![Chet\_Nichols\_III](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/e47774/32.png) [@Chet\_Nichols\_III](https://www.ruby-forum.com/u/Chet_Nichols_III)\ **Post date:** [November 14, 2007, 4:49am UTC](https://www.ruby-forum.com/t/efficiency-of-recursion-stack-level-too-deep/120146/1 "2007-11-14T04:49:57Z")
hi there- so i started running into a problem using recursion with ruby- it seemed a little too soon for me to be getting a stack overflow (‘stack level too deep (SystemStackError)’), so i wrote up a quick simple script to do some recursion: * * * #!/usr/local/bin/ruby def print\_depth num puts num print\_depth(num+1) end ## print\_depth 0 and sure enough, once im at a recursive depth of about 4,360, it errors out. i tried making num a global $num instead so it wasnt allocating memory on the stack each time for building a new ‘num’ object, but that only got me to about 4,500 until the overflow. to me, it seems a little low, especially for something this simple. my stack size is 10240. and, of course, when i up it to something like 20480, i get about double the recursive depth… but when i try the same thing in C: * * * #include \ void print\_depth(int num); int main() { print\_depth(0); } ## void print\_depth(int num) { printf("%d\n",num); print\_depth(++num); } i get a recursive depth of about 350,000 before it bombs out (which is what i’d expect more or less). i know C is super efficient and all, and ruby is truly object oriented, so each thing pushed on the stack is an object with its own set of methods, etc, so its by design going to take up more space, but i was wondering if there are any plans to do anything to help the efficiency of this at all? to be honest, i’ve only been using ruby for about a week now, and i totally love it. so, this e-mail really isn’t a complaint at all, just more of a question. if there’s already an answer (which there probably is), feel free to shout it out- i love everything i’ve seen and done so far with the language, so the more i know about it, the better! hope to hear from someone soon- thanks! chet ---
**Author:** ![Chet\_Nichols\_III](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/e47774/32.png) [@Chet\_Nichols\_III](https://www.ruby-forum.com/u/Chet_Nichols_III)\ **Post date:** [November 14, 2007, 4:34pm UTC](https://www.ruby-forum.com/t/efficiency-of-recursion-stack-level-too-deep/120146/2 "2007-11-14T16:34:33Z")
2007/11/14, Chet Nichols III [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > def print\_depth num > about 4,500 until the overflow. to me, it seems a little low, especially for > print\_depth(0); > truly object oriented, so each thing pushed on the stack is an object with > its own set of methods, etc, so its by design going to take up more space, > but i was wondering if there are any plans to do anything to help the > efficiency of this at all? > > to be honest, i’ve only been using ruby for about a week now, and i totally > love it. so, this e-mail really isn’t a complaint at all, just more of a > question. if there’s already an answer (which there probably is), feel free > to shout it out- i love everything i’ve seen and done so far with the > language, so the more i know about it, the better! hope to hear from someone > soon- thanks! You’ll find it in the archives. This issue comes up frequently. Basically Ruby is not good at recursion for exactly the reason you discovered. Cheers robert ---
**Author:** ![Chet\_Nichols\_III](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/e47774/32.png) [@Chet\_Nichols\_III](https://www.ruby-forum.com/u/Chet_Nichols_III)\ **Post date:** [November 14, 2007, 6:50pm UTC](https://www.ruby-forum.com/t/efficiency-of-recursion-stack-level-too-deep/120146/3 "2007-11-14T18:50:31Z")
On Nov 14, 2007 10:33 AM, Robert K. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > 2007/11/14, Chet Nichols III [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid): > > print\_depth(num+1) > > to something like 20480, i get about double the recursive depth… but when i > > try the same thing in C: > > … > > i get a recursive depth of about 350,000 before it bombs out (which is what > > i’d expect more or less). i know C is super efficient and all, and ruby is > > truly object oriented, so each thing pushed on the stack is an object with > > its own set of methods, etc, so its by design going to take up more space, > > but i was wondering if there are any plans to do anything to help the > > efficiency of this at all? > You’ll find it in the archives. This issue comes up frequently. > Basically Ruby is not good at recursion for exactly the reason you > discovered. Actually this is a problem with ruby, the implementation, rather than Ruby the language. Two comments. 1. Just this morning I listened to a podcast interview with Evan Phoenix and the differences between the invocation stacks in MRI and rubinius was discussed. Evan brought up something I hadn’t thought about. Because of the way MRI is implemented each Ruby method call will result in multiple C stack frames, so you need to multiply the recursion depth of that ruby program by some number to get the equivalent C stack depth. 2. There’s no good reason why a Ruby implementation couldn’t do tail-recursion optimization on the program in question, which would make that program much closer to an IDEAL infinite loop (i.e. one which would run out of non-cpu cycle resources much more slowly ) – Rick DeNatale My blog on Ruby [http://talklikeaduck.denhaven2.com/](http://talklikeaduck.denhaven2.com/) ---
**Author:** ![Chet\_Nichols\_III](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/c/e47774/32.png) [@Chet\_Nichols\_III](https://www.ruby-forum.com/u/Chet_Nichols_III)\ **Post date:** [November 14, 2007, 9:46pm UTC](https://www.ruby-forum.com/t/efficiency-of-recursion-stack-level-too-deep/120146/4 "2007-11-14T21:46:28Z")
On Nov 13, 10:49 pm, Chet Nichols III [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid) wrote: > i get a recursive depth of about 350,000 before it bombs out (which is what > i’d expect more or less). i know C is super efficient and all, and ruby is > truly object oriented, so each thing pushed on the stack is an object with > its own set of methods, etc, so its by design going to take up more space, > but i was wondering if there are any plans to do anything to help the > efficiency of this at all? Your wording seems to imply that you believe that each object has its own copy of all of its class’ methods. Although Ruby does allows you to add a method to a specific instance (the so-called “singleton method”), in general all instances of a class share one “copy” of the method. Each instance only needs to maintain its instance variables. Furthermore, objects, in general, tend to be stored on the heap, not the stack. References to the object may be stored on the stack. Ruby has some optimizations, such that Fixnums are handled in a special way and do appear on the stack. But they take the same amount of space as a reference anyway. So as far as the Ruby call stack is concerned. Rich DeNatale’s post in this thread is probably more accurate at describing why MRI (Matz’s Ruby implementation) has this problem. Other Ruby implementations, such as Rubinius, likely will not. Eric ==== Interested in hands-on, on-site Ruby training? See [http://LearnRuby.com](http://LearnRuby.com) for information about a well-reviewed class.