# Recursion and Tail Recursion

A function that calls itself is known as recursive function. This technique is known as recursion. A physical world example would be to place two parallel mirrors facing each other. Any object in between them would be reflected recursively.

#### How does recursion work in programming?

Here, the recurse() function is called from the body of recurse() function itself. Here’s how this program works.

``````fun main(args: Array)
{
recurse()
}

fun recurse()
{
recurse()
}

Example``````

Here, the recursive call continues forever causing infinite recursion. To avoid infinite recursion, if…else (or similar approach) can be used where one branch makes the recursive call and other doesn’t.

#### Find factorial of a Number using Recursion

``````fun main(args: Array)
{
val number = 4
val result: Long
result = factorial(number)
println("Factorial of \$number = \$result")
}
fun factorial(n: Int): Long
{
return if (n == 1)
n.toLong()
else
n*factorial(n-1)
}

Example``````
###### How this program works?

If you run the program, then this could be the step by step output:

1. factorial(4)
2. 4*factorial(3)
3. 4*(3*factorial(2))
4. 4*(3*(2*factorial(1)))
5. 4*(3*(2*1))
6. 24

#### Kotlin Tail Recursion

Tail recursion is a generic concept rather than the feature of Kotlin language. Some programming languages including Kotlin use it to optimize recursive calls.

###### What is tail recursion?

In normal recursion, you perform all recursive calls first, and calculate the result from return values at last (as show in the above example). Hence, you don’t get result until all recursive calls are made.

In tail recursion, calculations are performed first, then recursive calls are executed (the recursive call passes the result of your current step to the next recursive call). This makes the recursive call equivalent to looping, and avoids the risk of stack overflow.

###### Condition for tail recursion

A recursive function is eligible for tail recursion if the function call to itself is the last operation it performs.

``````fun factorial(n: Int): Long {
if (n == 1) {
return n.toLong()
}
else {
return n*factorial(n - 1)
}
}

Example 1``````

Not eligible for tail recursion because the function call to itself n*factorial(n-1) is not the last operation.

``````fun fibonacci(n: Int, a: Long, b: Long): Long {
return if (n == 0) b else fibonacci(n-1, a+b, a)
}

Example 2``````

Eligible for tail recursion because function call to itself fibonacci(n-1, a+b, a) is the last operation.

To tell for the compiler to perform tail recursion in Kotlin, you need to mark the function with tailrec modifier.

``````import java.math.BigInteger

fun main(args: Array) {
val n = 100
val first = BigInteger("0")
val second = BigInteger("1")
println(fibonacci(n, first, second))
}
tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger {
return if (n == 0) a else fibonacci(n-1, b, a+b)
}

Output
354224848179261915075``````

This program computes the 100th term of the Fibonacci series. Since, the output can be a very large integer, we have imported BigInteger class from Java standard library.

Here, the function fibonacci() is marked with tailrec modifier and the function is eligible for tail recursive call. Hence, the compiler optimizes the recursion in this case.

If you try to find the 20000th term (or any other big integer) of the Fibonacci series without using tail recursion, the compiler will throw java.lang.StackOverflowError exception. However, our program above works just fine. It’s because we have used tail recursion which uses efficient loop based version instead of traditional recursion.

#### Factorial Using Tail Recursion

The example to compute factorial of a number in the above example (first example) cannot be optimized for tail recursion.
Here’s a different program to perform the same task.

``````fun main(args: Array) {
val number = 5
println("Factorial of \$number = \${factorial(number)}")
}
tailrec fun factorial(n: Int, run: Int = 1): Long {
return if (n == 1) run.toLong() else factorial(n-1, run*n)
}

Output
Factorial of 5 = 120``````

The compiler can optimize the recursion in this program as the recursive function is eligible for tail recursion, and we have used tailrec modifier that tells compiler to optimize the recursion.

#### Questions

I hope the description was understandable and clear. But if you have still questions, then leave me comments below! 😉

Have a nice a day! 🙂