Tail Recursion in Scala : How is it different from Recursion ?

Lets first discuss ‘recursion’

In the world of programming, recursion is a technique that allows a function to call itself to solve a problem. It’s like a never-ending story, where each chapter leads to the next until the story is complete.

Let’s consider an example of computing the nth Fibonacci number using recursion in Scala:

def fibonacci(n: Int): Int = {

  if (n <= 1) n

  else fibonacci(n-1) + fibonacci(n-2)

}

//-----------
println(fibonacci(9)) // Output: 34

In the above example, we have define a function called fibonacci that takes an integer n as input and returns the nth Fibonacci number. The Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, starting from 0 and 1.

At the heart of the fibonacci function is a recursive call that computes the (n-1)th and (n-2)th Fibonacci numbers, adds them together, and returns the result. The base case is when n is less than or equal to 1, at which point we simply return n.

Recursion can be a tricky concept to wrap your head around at first, but with practice, its quite easy to understand.

Moving on… What is ‘tail recursion’ ?

Tail recursion is recursive technique that can help optimize your code by reducing the memory overhead associated with recursive calls. In tail recrusion, the recursive call is always the last step performed by the function.

Now, Lets look at two examples of tail recursion written in Scala :

Example 1: Computing the nth Fibonacci number

def fibonacci(n: Int): Int = {
  def fibHelper(n: Int, i: Int, j: Int): Int = {
    if (n == 0) i
    else fibHelper(n-1, j, i+j)
  }
  fibHelper(n, 0, 1)
}

//-----------
println(fibonacci(9)) // Output: 34

In the above example, we define a helper function called fibHelper that takes three arguments as input : the current value of n, the current value of the i^th Fibonacci number, and the current value of the (i+1)^th Fibonacci number. The base case is when n is 0, at which point we return the current value of i. Otherwise, we recursively call fibHelper with (n-1, j , i + j) and update the values of i and j accordingly.

Example 2: Computing the factorial of a number

def factorial(n: Int): Int = {
  def factHelper(n: Int, product: Int): Int = {
    if (n == 0) product
    else factHelper(n-1, n*product)
  }
  factHelper(n, 1)
}

//-----------
println(factorial(6)) // Output: 720

In this example, we define a helper function called factHelper that takes two arguments: the current value of n and the current value of the product of all the integers from 1 to n. The base case is when n is 0, at which point we return the current value of the product . Otherwise, we recursively call factHelper with (n-1, n*product) and update the product accordingly.

In both examples, the recursive calls are the last operations performed by the function, which allows the compiler to optimize the code and avoid creating new stack frames for each recursive call. This can lead to significant improvements in performance🚀, especially for large inputs.

Summary

To summarize, tail recursion is a special case of recursion where the recursive call is the last step performed by the function. This allows the compiler to optimize the code execution and reduce memory usage that improves performance and a reduces risk of stack overflow errors.

Feature	Recursion	Tail Recursion
Call Stack	Each recursive call creates a new stack frame	Only one stack frame is used throughout the recursion
Performance	Can be slow and memory-intensive for large inputs	Optimized by the compiler for faster execution🚀 and reduced memory usage
Stack Overflow	Possible if recursion calls go too deep	Unlikely to occur due to optimized memory usage