### 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 |