What exactly is Tail Recursion?
A Recursive Function is tail-recursive when the function executes a recursive call.
- Because tail-recursion can be optimised by the compiler, tail-recursive functions are thought to be superior to non-tail-recursive functions.
- Recursive operations are typically carried out by compilers using a stack. The parameter values for each recursive call are included in this stack along with all other relevant data. Information from a procedure is loaded onto a stack when it is called, and it is removed from the stack when the function is finished.
- As a result, the stack depth (the greatest amount of stack space used at any one time during compilation) is higher for non-tail recursive functions.
- The concept behind tail-recursive function optimization is straightforward: since the recursive call is the final statement of the current function, storing the stack frame of the current function serves no purpose.
Evolution of Tail Recursion :
- Tail recursion modulo cons is a generalisation of tail-recursion optimization proposed by David H. D. Warren in the context of a Strongly typed compilation as an explicitly set once language.
- Daniel P. Friedman and David S. Wise described (but did not name) it as a LISP compilation technique in 1974.
- It applies when the only operation left to perform after a recursive call is to prepend a known value in front of a list returned from it, as the name implies (or to perform a constant number of simple data-constructing operations, in general).
- This call would thus be a tail call except for the cons operation.
- However, appending a value to the end of a growing list on exit from a recursive call is equivalent to appending this value to the beginning of the growing list on entry into the recursive call.
- As if in an implicit accumulator parameter, the list is built as a side effect.
What does Tail Recursion mean in SCALA Language?
- Recursion is a method that split a problem into smaller subproblems and calls itself for each of them. That is, function calling itself.
- Tail-recursive functions outperform non-tail-recursive functions because tail-recursion can be optimised by the compiler.
- A recursive function is said to be tail-recursive if the recursive call is the last thing done by. There is no need to keep a record of the previous state.
- A package import scala.annotation.tailrec will be used in the programme for the tail recursion function.
Syntax :
tailrec def Func(P1, P2, ...): type = …
Example of a Tail Recursive Program :
import scala.annotation.tailrec
object Article
{
def GCD(n: Int, m: Int): Int =
{
@tailrec def gcd(x:Int, y:Int): Int=
{
if (y == 0) x
else
gcd(y, x % y)
}
gcd(n, m)
}
def main(args:Array[String])
{
println(GCD(12, 18))
}
}
Output for this Program is: 6
Here @tailrec is used for the gcd function that is the tail recursion function. By using tail recursion no need to keep a record of the previous state of the gcd function.
Is there any distinction between Recursion and Tail Recursion in Scala?
My answer would be YES, because in head recursion, the recursive call comes before other processing in the function (think of it happening at the top, or head, of the function). In tail recursion, the processing occurs prior to the recursive call.
Conclusion :
It’s trivial to exceed the capabilities of a head-recursive implementation, even with a straightforward task. Although the tail-recursive implementation may appear less natural, it is unquestionably something to strive for in some circumstances. When it comes to code optimization and informing us when an implementation is not tail-recursive, the Scala compiler performs a good job.
