Recursion or iteration?

Question

I love recursion. I think it simplifies things a lot. Another may disagree; I think it also makes the code a lot easier to read. However, I've noticed that recursion is not used as much in languages such C# as they are in LISP (which by the way is my favorite language because of the recursion).

Does anybody know if there is any good reasons not use recursion in the languages such as C#? Is it more expensive than iteration?

Solution 1

Are they more expensive than iterations?

Yes they are. Many Lisp variants support the idea of a "tail-call optimisation" which allows many uses of a recursive function call to be converted into an iterative one (this is simplifying a bit). If tail-call is not supported, then a recursive function call will use progressively more memory on the stack.

Solution 2

Are they more expensive than iterations?

Yes they are. Recursion requires creating a new stack frame along with a call and return whereas iteration generally only requires a compare and branch making it substantially faster; however, compilers can perform tail-call optimization on certain recursive calls (namely tail calls) which allow them to reuse the stack frame making the recursive call much less expensive and effectively turning them into iteration. Scheme actually requires that scheme compilers implement tail-call optimization.

Solution 3

The compiler and the architecture of modern CPUs can do lots of optimizations with iteration that they can't do with recursion. For example, the ability of the processor to do optimistic computation. When the processor finds an iteration space it knows how long it will take. From the beginning, there is no real need to check each time before starting the next loop. So, they pipeline the operations. Since most CPUs can do several operations at the same time (through pipelining), you can solve the iteration space in less time than the recursion. This is even with tail-optimization because the CPU is actually processing about 4 loops at a time (for a x4 performance gain). This gain will depend on the architecture of the CPU. The architecture is likely to be a big part of the gain, with next gen CPUs pushing gains even further than that.

The true problem with recursion is that our hardware is VonNeumann based (achievable variant of the Turing machine), and not Lisp machines, although there are a few specialized Lisp hardware, you won't find any desktops with it :)

Solution 4

Functional languages such as Lisp and F# can implement many tail recursive functions internally as loops and are able avoid the stack overhead of a function call. C# doesn't have support for tail recursion, although F# does.

Solution 5

There are many pros and cons to using recursion. Definitely the code simplicity is the biggest one which also lends itself to better code maintainability and less bugs.

The biggest danger to recursion are edge cases were the algorithm spins out of control to break the function stack limit. Some languages, Progress's ABL language for one, has a parameter for the highest level of nested calls allowed. These are usually low and adding recursion to the mix could make an application break that limit.

In short, recursion should always be implemented with tight termination cases otherwise it can be very difficult to debug (because of unpredictability) and can cause serious issues in production code.

For the concerns with memory and speed, unless this is a method itself is short (time wise) being called many times it really doesn't matter what the performance is.

Example: If you use recursion to scan all the files and folders of a hard drive the performance impact that the recursion does is minuscule to the time it takes to hit the hard drive and grab the file system information. In this case recursion is probably preferred over iterative processing.

Another example: If you scan the nodes of a tree structure, an iterative process maybe more beneficial because we are not involving the function stack as much which means we are hitting less memory and probably letting the hardware use more caching. See Robert Gould's response for more details.

View more solutions

Comments

[Jules]

Many Lisps don't support tail calls.

[Aaron Maenpaa]

@julesjacobs You're probably right, the one I wrote certainly didn't; however, it's good to note that Scheme requires it.

[strager]

Functions are copied to the stack? I think you mean function /pointers/ are copied to the stack. Stack overflow is more common with managed code (Java, .NET) because the stack is no different from the heap (speaking generally) when it comes to unmanaged C/C++ (where read/write from unalloc'd memory

[strager]

causes a segmentation fault). Also, don't think all situations are simple for(x = 0; x < 42; ++x). Recursion usually isn't called for in those cases. I agree it is "subjective," but I think the choice between recursion and iteration is dependent on who's going to maintain the code.

[palantus]

We need an award for the longest sentence ever posted on SO. ;)

[Theo Orphanos]

... longest ever comprehensible sentence, at least.

[plinth]

C# doesn't specify it, but the underlying CLR includes a tail call instruction, therefore it is a reasonable optimization. NB: as of .NET 2.0, tail call was SLOWER than a regular call.

[Karl]

Comprehensible indeed, I didnt even notice the run-on until mmyers pointed it out, but I'm often guilty of that style, so I am immune to it. See?

[Greg]

Any good compiler should optimize away tail calls. Pity that so many aren't good.

[Robert Gould]

I'm a literary freak apparently, totally unrolled that sentence there, wow.

[nsayer]

Well, yeah, but XSLT sort of admits to no alternative. The code up there is pseudocode. With XSLT, of course, it would all be <xsl:template> nodes and stuff.

[Peter Mortensen]

It would be interesting with actual XSLT.

[Erik Reppen]

A functional language can have features that make it near impossible to tail-call optimize. In the case of JavaScript these features have been deemed "not worth it" but it will likely be years before the features are finally dropped.

[2-bits]

Mmmmmmmm..... ehhhhh... I don't know about this. For one, sure, Parallel.For isn't recursive, but the functions you pass to it could be (if you are operating on lists of lists, for instance). For example, you could launch a Task for for each branch of a tree, and await them and still make a recursive call. It's possibly slightly less intuitive but I don't know if I would say impossible/much harder.