Hazzards of Recursion

I think that I will be not the only one and definitely not the first one to claim that recursion is a an educational milestone in Computer Science disciplines. When it comes to understanding recursion, that's one of the "truth moments" in your Computer Science career. If you don't feel comfortable with recursion and don't understand it - you should probably leave the field. Some people claim the same about pointers, but well, even when I find it to be true, nowadays pointer arithmetic plays much less significant role then before, when computer had several hundreds of kilobytes of memory and being able to do pointer arithmetic was considered  a "must master" for any programmer. I guess at a time there was really no other choice at all.

This leads to much more interesting and broader subjects. I remember those times when we were talking of buying 512MB of RAM, creating a RAM-drive and loading there Windows98, so it will run smoother. Well, we were just kids at a time. Nevertheless what I wanted to say was about recursion.

Every CS student has heard at least once during his career "Recursion is cool, however - DON'T use it!". Some might wonder well, why is it so? Well - in fact the recursion is cool indeed, BUT is slow as hell! I have compared just for fun some code that was using a recursion versus non recursive code, and it appeared that non recursive code was about 10 times (!!!!) faster for significant amount of computation. And when I say significant, I mean several hours of runtime.

One must ask - but why? And the answer would be - this is due to stack frames allocations of course. It turns out that it is quite costly to open a new stack frame. I believe there are other reasons as well, which maybe depend on the programming language, but this would be the most obvious one. So kids, don't say I didn't warn you - don't try this at home!