Menu
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?
491
In head recursion , the recursive call, when it happens, comes before other processing in the function (think of it happening at the top, or head, of the function). In tail recursion , it's the opposite—the processing occurs before the recursive call.
Different types of the recursionDirect Recursion. Indirect Recursion. Tail Recursion.
While tail-recursive calls are usually faster for list reductions—like the example we've seen before—body-recursive functions can be faster in some situations. That's often true when mapping over a list, where the function takes a list and returns a list without reducing it to a single value.
In tail recursion, there is no other operation to perform after executing the recursive function itself; the function can directly return the result of the recursive call. In non-tail recursion, some operations need to be performed using the returned value of the recursive call.
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:
83
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
