Learn about the keyword “tailrec” in Kotlin to write a function that calculates 1,000,000 factorials

Tailrec is a keyword added to Kotlin from version 1.0, it stands for the phrase “tail recursion” – ie tail recursion. Understanding and using the keyword tailrec in Kotlin will make your programming job much more interesting. Since there may be people who do not know what recursion and tail recursion are, let’s first briefly talk about recursion.

What is recursion?

According to the Vietnamese Wikipedia:

Recursion (English: recursion) is a method used in computer programs in which a function calls itself.

An example with recursion is the factorial function. I always know n! = n * (n - 1)! so we can write a recursive function like this:

What is tail recursion?

In the above example when calling factorial (5) the program will do the following:

It is easy to see that factorial (5) has to wait for factorial result (4) to continue calculating, factorial (4) has to wait for factorial result (3) … Because recursive call is done The calculation is performed first, so this is called a head recursion. Because each recursive call must save the current function state to the call stack to wait for further calculations, in case the call stack is too large, the program will encounter a stack over flow error.

With tail recursion, all operations will be performed before calling recursion. The above function can be rewritten by tail recursion as follows:

When running the above program with factorial (5), it will do the following:

Because the calculation is definitive, when recursively calling the status of the current function does not need to be stored in the call stack for further calculations, stack over flow will be limited.

This means that the tail recursion runs a circuit from the first function to the last function and gets the result, while the first recursive must run from the first function to the last function and then return to the first function to get the get results (see illustration). Therefore, in essence, tail recursion is like a loop and this is why the keyword tailrec in Kotlin was born.

What is the keyword “tailrec” in Kotlin?

As a language that was born later and is still in the process of being developed, Kotlin has (is and will continue to) learn and inherit cool features from earlier languages. tailrec in Kotlin is also learned from Scala’s @tailrec annotation. So, what does Kotlin’s tailrec keyword do?

Even with tail recursion, when calling recursively, a new memory area is created to execute this recursive call, while the old memory areas have not been freed. So the allocated memory area will increase with the number of recursive steps. Although there is no need to save the state of the previous functions, the amount of memory allocated is too much, it can still be stack over flow, otherwise it is extremely wasteful because the memory in previous calls is not. still needed but still not released immediately. Therefore, the tailrec keyword is created to take advantage of the available memory for the next recursive call. That is, we only need one memory device for any n recursive call.

Why is it so magical? Actually we don’t have any magic here. The tailrec keyword in Kotlin is still essentially just an annotation informing the compiler that with the function applied to this keyword, it will be converted from recursive to loop form, i.e. when done It only runs inside that function.

Accordingly, the tail recursive function is added with the tailrec keyword below

After compilation will become the following categories:

As you can see, the original tail recursive function has been completely converted into a regular function with a (recursive) loop. Also, when you apply tailrec to a function that is not written in a recursive form, the compiler will give an error, with IntelliJ and Android Studio, there will be a live warning for you.

Rewrite the factorial function in Kotlin

The following function can calculate 1,000,000! without stack over flow regardless of how many times recursion is super super due to the tailrec keyword. However, it runs long and scattered.

The result of factorial(1000_000) is

Updated in version 1.4

According to issues KT-31540 , from version 1.4, tailrec will be slightly revised because some cases are similar to the following:

When we run, we will see the result

This makes the user feel unreasonable, but the result should be as follows (when removing the keyword tailrec ):

This is because z = inc() was called before y = inc() because the JetBrains devs made the assignment from the last parameter back to the beginning. While it should be assigned from beginning to end. So now if you assign the default value to the parameter to remember the value of the tailrec function is a non-constant value, you will get a warning for this.

summary

This article introduces an overview and most understandable about the keyword tailrec in Kotlin. Hope to be helpful to you in programming with the beloved Kotlin language. If you have any questions, please leave a comment below this article.

See more at: https://kotlinlang.org/docs/reference/functions.html#tail-recursive-functions