Recursion or iteration?
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?
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.
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.
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 :)
链接地址: http://www.djcxy.com/p/80526.html上一篇: 是否有可能使用continuation来使foldRight尾部递归？
下一篇: 递归或迭代？