Which is more efficient recursion or loops?

Question

I am curious which is more efficient for iteration. I am using one to break up a parse a string into a List. Is recursion more CPU efficient or is looping? Is either more memory efficient? By looping, I am referring to for, for each, do while, while, and any other types. Out of these loops which are more efficient? Or are they all equally? Just curious.

Answer 1

You can't make a general statement on that. It depends on what the loop is doing, how you have coded it ... and how well the JIT compiler is able to optimize it. It can also make a difference what kind of list the loop is iterating over. The same goes for recursion.

To get a reliable answer, you need to examine the various alternatives on a case-by-case basis, and (carefully!) benchmark the specific examples on your Java platfrom.

Recursion in Java has the problem that each level of recursion requires a stack frame, and Java stacks have bounded size. If you have to recurse too deeply, your algorithm will crash with a StackOverflowError. (Current generation Java platforms do not implement tail call optimization.)

You also want to avoid doing index-based iteration (e.g. for i = 0 to size - 1) over a LinkedList, because that will give you O(N^2) behaviour.

---

Fortunately, the difference in performance for the different kinds of Java loop usually doesn't make enough difference to matter. So (modulo the stack depth issue, and the issue of choosing the correct List class), you can safely leave performance to "later" ... and deal with it if-and-only-if it becomes necessary to do performance optimization.

Answer 2

Iteration is generally going to be more efficient. Recursion requires more memory (to set up stack frames) and time (for the same). However, if you can set up tail recursion, the compiler will almost certainly compile it into iteration, or into something which is similar, giving you the readability advantage of recursion, with the performance of an iterative method.

In some situations an iterative solution will be implemented by essentially maintaining your own stack, so the difference may be minimal.

See Is recursion ever faster than looping? for more details.