Tail recursion vs head classic recursion
recursion, scala
Solution
Tail Recursion == Loop
You can take any loop and express it as tail-recursive call.
Background: In pure FP, everything must result in some value. `while` loop in scala doesn't result in any expression, only side-effects (e.g. update some variable). It exists only to support programmers coming from imperative background. Scala encourages developers to reconsider replacing `while` loop with recursion, which always result in some value.
So according to Scala: Recursion is the new iteration.
However, there is a problem with previous statement: while "Regular" Recursive code is easier to read, it comes with a performance penalty AND carries an inherent risk of overflowing the stack. On the other hand, tail-recursive code will never result in stack overflow (at least in Scala*), and the performance will be the same as loops (In fact, I'm sure Scala converts all tail recursive calls to plain old iterations).
Going back to the question, nothing wrong with sticking to the "Regular" recursion, unless:
- The algorithm you are using in calculating large numbers (stack overflow)
- Tail Recursion brings a noticeable performance gain
Problem
listening to Scala courses and explanations I often hear: "but in real code we are not using recursion, but tail recursion". Does it mean that in my Real code I should NOT use recursion, but tail recursion that is very much like looping and does not require that epic phrase "in order to understand recursion you first need understand recursion" . In reality, taking into account your stack.. you more likely would use loop-like tail recursion. Am I wrong? Is that 'classic' recursion is good only for education purposes to make your brain travel back to the university-past? Or, for all that, there is place where we can use it.. where the depth of recursion calls is less than X (where X your stack-overflow limit). Or we can start coding from classic-recursion and then, being afraid of your stack blowing one day, apply couple of refactorings to make it tail-like to make use even stronger on refactoring field? Question: Some real samples that you would use / have used 'classic head' recursion in your real code, which is not refactored yet into tail one, maybe?