Tail Recursion in SCALA

What is Tail Recursion?

A Recursive Function is tail-recursive when a recursive call is the last thing executed by the function.

* The tail-recursive functions are considered better than non-tail recursive functions as tail-recursion can be optimized by the compiler.

* Compilers usually execute recursive procedures by using a stack. This stack consists of all the pertinent information, including the parameter values, for each recursive call. When a procedure is called, its information is pushed onto a stack, and when the function terminates the information is popped out of the stack.

* Thus for the non-tail-recursive functions, the stack depth (maximum amount of stack space used at any time during compilation) is more.

* The idea used by compilers to optimize tail-recursive functions is simple since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use.

History of Tail Recursion :

* Tail recursion modulo cons is a generalization of tail-recursion optimization introduced by David H. D. Warren in the context of a compilation of Prolog, seen as an explicitly set once language.

* It was described (though not named) by Daniel P. Friedman and David S. Wise in 1974 as a LISP compilation technique.

* As the name suggests, 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 (or to perform a constant number of simple data-constructing operations, in general).

* This call would thus be a tail call save for ("modulo") the said cons operation.

* But prefixing a value at the start of a list on exit from a recursive call is the same as appending this value at the end of the growing list on entry into the recursive call

* Thus building the list as a side effect, as if in an implicit accumulator parameter.

What is Tail Recursion in SCALA Language?

* Recursion is a method that breaks the problem into smaller subproblems and calls itself for each of the problems. That is, it simply means function calling itself.

* The tail-recursive functions are better than non-tail-recursive functions because tail-recursion can be optimized by the compiler.

* A recursive function is said to be tail-recursive if the recursive call is the last thing done by the function. There is no need to keep a record of the previous state.

* For tail recursion function a package import scala.annotation.tailrec will be used in the program.

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 difference between Recursion and Tail Recursion in Scala?

My Answer for this would be YES, because 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.

Conclusion :

* Even with a simple problem, it’s easy to reach the limits of a head-recursive implementation. Although the tail-recursive implementation might look less natural, it’s definitively worth aiming for in certain situations.

* The Scala compiler does a good job of optimizing the code and warning us when an implementation is not tail-recursive.