CODEWITHSUNDEEP
javarecursiontail-recursion
believer
believer

Reputation: 43

Should I use tail recursion in java even if it does not optimize tail-recursion

After having read online, I have found that java does not optimize tail-recursion. So, is there any point in using it, if head and tail recursion would yield the same result.

Moreover, are loops always better in performance than recursion ( tail and head); as it is sometimes easier to use recursion without thinking about the iterations. Please do tell if I should use loops.

Please correct me if I am wrong as I have just started with recursion.

Upvotes: 2

Views: 122

Answers (1)

rzwitserloot
rzwitserloot

Reputation: 102814

Yes, the performance of any recursive algorithm in java is almost always significantly worse than rewriting the same thing using a loop. Using loops is generally always just as easy:

  • Make a stack or deque object.
  • Make a class that represents all relevant state.
  • Write a loop that grabs stuff off the stack or deque and operates on it.
  • As part of 'operating on it', you are free to pile on new jobs - analogous to calling yourself.

That 'formula' should work for any recursive algorithm.

However, the vast majority of code you write just doesn't matter, performance-wise. Quite literally, if your app is having any measurable effect on the CPU at all, it's almost always that 99% of the CPU resources your app is using up are being used up by 0.1% of your entire codebase.

The job then is obviously to [A] find that 0.1% and [B] make it more efficient.

The remaining 99.9% just do not matter. This is not a 'death by a thousand cuts' situation - it really doesn't matter. You can write code to be 10 to 100x less efficient than it could be, and even if you make such a mistake tons of times, as long as it isn't in that 0.1% crucial path, you'd never notice, and nor will your users.

So, in that sense, if you think it's easier to write your code and easier to read it if you use recursion, knock yourself out. Just know that if your profiler is telling you that this recursive algorithm is in that 0.1% (the crucial path), yes, step 1: Rewrite away from recursion.

Sidenote: As long as you don't recurse too far, JVMs can optimize quite a bit. Some VMs, like azul, go so far as to eliminate a bunch of your stack trace if it is repetitive (recursive algorithms have repetitive stack traces). Thus, even a recursive algorithm in java can be fine, performance wise. It's just a lot harder to reliably get this result, as you're now relying on the optimizations made in custom VM implementations.

Upvotes: 4

Related Questions