2

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.

Improve this question
2
  • 1
    "are loops always better in performance than recursion" that certainly would depend on what you are doing Commented Jul 26, 2021 at 12:58
  • 1
    AFAIK loops are always better in performance than recursion since you don't have the function call overhead (please someone correct me if I'm wrong here), this is why tail recursion is optimized as loops by some compilers. However the whole point writing a recursive function is readability, so I would definitely write the algorithm as recursive if it's more readable unless the performance is critical on this specific part. Commented Jul 26, 2021 at 13:11

1 Answer 1

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for your detailed answer! Perhaps too detailed for me, a beginner. However, I did understand the usage.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.