From: Rob Biedenharn <Rob@...>
Date: 2009-10-01T06:17:31+09:00
Subject: Re: SystemStackError: stack level too deep > how make it deeper?

On Sep 30, 2009, at 5:02 PM, Jason Roelofs wrote:
> On Wed, Sep 30, 2009 at 4:56 PM, Joshua Muheim <forum@josh.ch> wrote:
>>> Or a problem from Project Euler... ;-)
>>> http://projecteuler.net/index.php?section=problems&id=45
>>>
>>> real  0m0.639s
>>> user  0m0.623s
>>> sys  0m0.008s
>>>
>>> And my solution (in Ruby) could even be made more efficient.  
>>> However,
>>> it uses a constant amount of space (i.e., no recursion at all, just
>>> some nested loops).
>>>
>>> -Rob
>>>
>>> Rob Biedenharn    http://agileconsultingllc.com
>>> Rob@AgileConsultingLLC.com
>>
>> Yeah, it's from Project Euler (our professor is just too lazy to  
>> create
>> his own tasks...).
>>
>> Your solution sounds interesting; would you mind posting it here? I
>> won't steal it; we don't have to submit perfect solutions, it's more
>> sort a thinking-task where we're told to deliver possible solutions.
>> --
>> Posted via http://www.ruby-forum.com/.
>>
>>
> So I get put down for suggesting the very thing Rob did, who gets  
> praise?
>
> If you don't want long-running code crashing, don't do it recursive  
> in a
> language like Ruby. You will run out of memory, and you will crash.  
> There
> are very few, if any, algorithms normally written recursively that  
> can't be
> written iteratively.
>
> Jason


I'm on exactly the same page as Jason. The problem does not even need  
a recursive algorithm. (Well, except that it's not the Ruby language  
that is recursive, but the algorithm that you attempted to write *in*  
Ruby.)

Your attempt isn't really too far off, however. I'll point out that  
your algorithm is "tail recursive" and that's partly why you run out  
of stack space in a language like Ruby, but in a language optimized  
for tail recursion it might have worked. Think about what that means  
and how you could restructure your code to avoid making a new function  
call if the current pair is not a solution.  (Hint: How would you  
search for the solution standing at a blackboard/whiteboard?)

-Rob

Rob Biedenharn		http://agileconsultingllc.com
Rob@AgileConsultingLLC.com