Is recursive code slower than non-recursive code?

Question

Now I'm only a novice programmer, but what my friends that are studying programming tell me is that recursive code is a good thing, it leads to less code duplication and it looks more elegant.

Now it may be so, but everytime I've tried my hand with recursive code I've always found it to be significantly slower than non-recursive code, I'm not sure if it's something about the ways I've used it but I highly doubt it, I've used it for fairly simply thing's like Collatz Conjecture and Fibonacci number generation but whenever I've compared it against normal iterative code the recursive approach will consistently clock at around twice the time of the iterative solutions.

Answer 1

It is good to at least understand how recursion works, because some algorithms are naturally recursive and thus much easier to express using recursion.

Also, recursive algorithms (or implementations) are not inherently slower than iterative ones. In fact, every recursive algorithm can be implemented by an equivalent iterative implementation at the cost of having to keep track some intermediate/temporary values yourself, where the recursive version automatically keeps track of those in the function call stack.

One example of a naturally recursive algorithm is if you want to apply an operation to all the nodes of a tree. The most natural implementation here is to have a function that performs the operation on one node and calls itself recursively for each of the children of the node.

---

For some algorithms, like calculating a Fibonacci sequence, recursion seems natural, but a naive implementation will be much slower than an iterative implementation, because the recursive version keeps re-doing the same work over and over again. This just means that for those particular algorithms, recursion may not be the best choice, or that you need to use some techniques to remember intermediate values that might be needed again elsewhere in the algorithm.

For other algorithms, in particular those that use divide-and-conquer tactics, you will find that you need a stack to keep track of some thing in the iterative solution. In those cases, a recursive version is much cleaner, because the stack handling becomes implicit.

Answer 2

Recursion is slower and it consumes more memory since it can fill up the stack. But there is a work-around called tail-call optimization which requires a little more complex code (since you need another parameter to the function to pass around) but is more efficient since it doesn't fill the stack.

Unfortunately C# does not support this so I would suggest you to use recursion with care, because you might get stack overflow for large values.

As a conclusion, in functional languages you only have recursion and have to deal with it; but in imperative languages iteration is more natural and more efficient. The majority of the most-used imperative languages either does not support (Java, C#, Python) or does not guarantee (C, C++) tail call optimization.