How to make use of recursion in Kotlin.

Since Kotlin is a multi-paradigm language, we can also avoid using for loop and use recursion instead. This blog, I will show a little trick to do a TCO in Kotlin.

The Imperative Programing is normally defined by thing four things:

Sequence, Selection, Iteration, Subroutine

But in the FP, it has no

Let me writing a short recursive function which will find a factorial result:

```
fun factorial(num: Double): Double {
when (num) {
1.0 ->
return num
else ->
return factorial(num - 1) * num
}
}
```

This code is working fine. It can give you an expected result but what if I tell you that it could cause you a problem?

StackOverflow Error

Every time when we call a function, one stack frame will be created. Let’s say that I call this function 50,000 times which will create 50,000 frames in stack and when it reach the heap size then this error will happen. Moreover, in term of the performance, this code will also give you a bad result.

Tail call optimization

To solve the problem, there is the way we can do to our code to a tail recursion which that means in the line that function call itself must be the last line and it must not have any calculation after it. For example:

```
fun myfunc(num : Int = 20): Int {
if(num == 0){
return 0
} else {
return myfunc()
}
}
```

The above function is a tail recursion function. Here is another sample which is **NOT** a tail recursion.

```
fun notaTailRecursionFunction(num : Int = 20): Int {
if(num == 0){
return 0
} else {
return notaTailRecursionFunction() + 10
}
}
```

The function above, even it return itself at the last line but it still does some calculate ( + 10) which isn’t correct.

Let’s optimize the factorial function:

```
private fun factorial(num: Double): Double {
return factorial(num, 1.0)
}
fun factorial(num: Double, result: Double): Double {
when (num) {
0.0 ->
return result
else ->
return factorial(num-1, num * result)
}
}
```

I simply split it as two functions and make sure both of them follow the tail recursion concept.

Is that all?

```
private fun factorial(num: Double): Double {
return factorial(num, 1.0)
}
tailrec fun factorial(num: Double, result: Double): Double {
when (num) {
0.0 ->
return result
else ->
return factorial(num-1, num * result)
}
}
```

Let’s run the program and see the stack frame:

So every time you like to do a recursion, 2 things that need to consider which are:

- Make the function as tail recursion
- Put tailrec in front of your function.

If your function isn’t a tail call but you put

Reference

Like
217 likes

Share:

From us to your inbox weekly.