Io doesn't have tail call elimination or many other facilities to help you out here. Io is inherently an imperative language, and not designed for efficient recursion. That said, Io takes the design decision that running out of stack space at a fixed low level, is not a good idea, and we'd prefer to be a little slower but allow you to recurse much longer. By this effect, what slows down recursion in Io is when we're about to run out of stack space, we create another object to act as part of the composite "call frame" and chain it together with the previous. Thus when you do exhaust stack space, we have another object of unlimited extent waiting there to catch your overflow. In this respect, it puts much more pressure on the allocator and the garbage collector, which is what makes recursion slower in Io. Fun fact, the more you recurse, the worse the effect is, as I'm sure is understandable based on my description above.
While you can recurse into infinity*, that doesn't mean you should. As with in languages like C and otherwise, you should probably find an iterative algorithm if possible than a heavily recursive algorithm.
* - Assuming you have an infinite amount of addressable RAM, and a backing store of infinite size
Regards,
Jeremy Tregunna
Io doesn't have tail call elimination or many other facilities to help you out here. Io is inherently an imperative language, and not designed for efficient recursion. That said, Io takes the design decision that running out of stack space at a fixed low level, is not a good idea, and we'd prefer to be a little slower but allow you to recurse much longer. By this effect, what slows down recursion in Io is when we're about to run out of stack space, we create another object to act as part of the composite "call frame" and chain it together with the previous. Thus when you do exhaust stack space, we have another object of unlimited extent waiting there to catch your overflow. In this respect, it puts much more pressure on the allocator and the garbage collector, which is what makes recursion slower in Io. Fun fact, the more you recurse, the worse the effect is, as I'm sure is understandable based on my description above.
While you can recurse into infinity*, that doesn't mean you should. As with in languages like C and otherwise, you should probably find an iterative algorithm if possible than a heavily recursive algorithm.
* - Assuming you have an infinite amount of addressable RAM, and a backing store of infinite size
Regards,
Jeremy Tregunna
Post by trevor_landauI'm running through the 7 langs 7 weeks book and am working on the 1st question self study question concerning writing a fibonacci sequence.
I've written one using a for loop which is quite fast and another using recursion which is super slow after I try to use the sequence on a number passed say 20. If i try 42, it won't ever print or at least I don't wait long enough to let it print.
Am I doing something wrong?
fibRec := method(num,
if(num < 2,
return num,
return fibRec(num - 1) + fibRec(num - 2)
)
)
fibRec(1) println
fibRec(4) println
fibRec(17) println
fibRec(42) println # Pretty much never executes
Thanks.