Tail Recursion in Scala

Tail recursion is an optimization technique used in functional programming where a recursive function is transformed to use a loop construct, thus making it more efficient. In a tail-recursive function, the recursive call is the last operation in the function. This allows the Scala compiler to reuse the current function's stack frame for the next function call, preventing a stack overflow error in scenarios with many recursive calls.

Scala's standard library provides an annotation @tailrec which ensures that the function is tail-recursive. If the function isn't tail-recursive, the compiler will throw an error.

Simple example without tail recursion:

Here's a simple function to compute the factorial of a number, but it's not tail-recursive:

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

If you call factorial(5000), you'll likely get a StackOverflowError.

Making it tail-recursive:

To make the above function tail-recursive, we can introduce an accumulator:

import scala.annotation.tailrec

@tailrec
def factorialTailRec(n: Int, accumulator: Int = 1): Int = {
  if (n <= 0) accumulator
  else factorialTailRec(n - 1, n * accumulator)
}

Now, factorialTailRec(5000) will compute without causing a stack overflow.

Points to Note:

Use of Accumulator: In the tail-recursive version, we introduced an accumulator to hold the intermediate results. This is a common pattern when converting a function to be tail-recursive.
@tailrec Annotation: The @tailrec annotation is used to instruct the compiler to check that the function is tail-recursive. If it isn't, the compiler will generate a compile-time error. This is especially useful while refactoring to ensure that the tail-recursive nature of a function isn't accidentally broken.
Limitations: Not every recursive function can be transformed to a tail-recursive function. For some algorithms, tail recursion might not be straightforward or possible.

Tail recursion is an essential concept in functional programming, especially in languages like Scala, where immutability and recursion are often preferred over loops and mutable state. Properly applied, tail recursion allows developers to write safe, efficient, and idiomatic recursive functions.

How to write tail recursive functions in Scala:
- Description: To write a tail recursive function in Scala, ensure that the recursive call is the last operation in the function and annotate the function with the @tailrec annotation.
- Code:
```
import scala.annotation.tailrec

@tailrec
def factorialTailRec(n: Int, acc: Int = 1): Int = {
  if (n <= 0) acc
  else factorialTailRec(n - 1, n * acc)
}
```
Tail recursion examples in Scala:
- Description: Tail recursion is commonly used for tasks like computing factorials, calculating Fibonacci numbers, and traversing tree structures.
- Code:
```
// Example: Tail recursive Fibonacci
@tailrec
def fibonacciTailRec(n: Int, a: Int = 0, b: Int = 1): Int = {
  if (n <= 0) a
  else fibonacciTailRec(n - 1, b, a + b)
}
```