Link Details

"Never hire anyone who codes a factorial function with recursion" ;)

Write me an iterative version. In Haskell.

fac n = snd (until ((>n) . fst) (\(i,m) -> (i+1, i*m)) (1,1))

?

from: http://www.willamette.edu/~fruehr/haskell/evolution.hs

Wow. I had to try that out to believe you. ;)

Much more readable as the recursive version anyway..

Here's rot13 in Haskell:

[chr(mod (ord a-ord 'a'+13) 26+ord 'a') | a <- "bushpx"]

..runs away

hehehe ;)

The problem is, he's rewritten explicit recursion with implicit recursion - he's just using his own stack to do the recursion now instead of using the built-in call stack. Technically it's still recursion.

It's a little bit more efficient*, since it doesn't need to waste time OR space pushing and popping various registers, arguments and variables on the new stack frame. Also it's probably better because the memory is being allocated on the heap, not the stack, so there's more to go around. However, it's still recursive, and ultimately it will still eat up the memory (it's linear space instead of constant space).

*Note: I'm thinking about this in terms of C, I'm not sure how C# does things internally but I'm sure it's similar.

A better (but less general) approach would have been to identify tail recursion (and perhaps even use several techniques to create tail recursion, if not immediately visible), and then it's possible to convert it into a truly iterative case, taking constant space. (Read up on tail recursion).

Most good optimising compilers for any language will automatically identify obvious tail recursion and convert it into iteration for you. So often it is enough to just make your recursive calls tail-recursive, to ensure constant space.

Of course, not all algorithms can be made tail-recursive (an obvious example is QuickSort, which needs to recurse twice). In the case of QuickSort, the best optimisation would be to follow this article and make an explicit stack.

Recursive functions are usually a pretty simple way to accomplish things quickly. One of the methods I use to make sure I don't end up running out of memory is passing in a maxdepth parameter, that ends the recursion.

It really depends on what you are trying to accomplish, though... I'm typically not needing to recurse more than a few levels.