# Why is \`tailrec\` a modifier keyword applied at the function level?
**URL:** https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886
**Category:** Language Design
**Created:** [December 20, 2017, 2:02am UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886 "2017-12-20T02:02:49Z")
**Posts on this page:** 16
**Page:** 1
### Author:  [@luisrayas3](https://discuss.kotlinlang.org/u/luisrayas3)
#### Post date: [December 20, 2017, 2:02am UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/1 "2017-12-20T02:02:49Z")
There are actually 2 parts to this question:
1. `tailrec`, IMHO, stands out as an oddball in the modifier keyword group as it has no effect on semantics, instead operating in compiler-space optimization world. Why isn’t it e.g. an annotation?
2. It seems to me that applying it at the function declaration level is restrictive. Consider the following:
```auto
tailrec fun f(x: Int): Int = when {
x <= 10 -> x
x % 2 == 1 -> f(x - 7) + 1
else -> f(x + 1)
}
```
In this case I have no way to specify that I intend one branch to be tail recursive and the other not to be. A related issue is that I may actually intend for one such branch to be tail recursive but the function as a whole is tail recursive so long as some other branch makes a tail recursive call.
An approach that seems better all around (to me) would be an annotation at the expression level:
```auto
fun f(x: Int): Int = when {
x <= 10 -> x
x % 2 == 1 -> f(x - 7) + 1
else -> @TailRec f(x + 1)
}
```
it just seems like the “right” place to put it. The compiler’s job is very straightforward as well, probably even simpler than its current responsibilities.
As a bonus [and from [Kotlin: Tail recursion for mutually recursive functions - Stack Overflow](https://stackoverflow.com/questions/35714683/kotlin-tail-recursion-for-mutually-recursive-functions) I gather that the JVM doesn’t support mutual recursion (or “proper tail calls” in the general case) but if it were to be supported in the future] this approach could be easily extended:
```auto
fun f(x: Int): Int = if (x > 100) @TailCall g(x / 2) else x
fun g(x: Int): Int = @TailCall f(x + 4)
```
---
### Author:  [@code2fun](https://discuss.kotlinlang.org/u/code2fun)
#### Post date: [April 8, 2019, 9:27am UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/2 "2019-04-08T09:27:34Z")
Hi,
It is a little bit late but I want to answer it anyway. The problem here is not kotlin. The problem here is the written code. It is always desireable to prefer an iterative process over a recursive one. So you have to transform it into an iterative one. So I did it!
From:
```auto
tailrec fun f(x: Int): Int = when {
x <= 10 -> x
x % 2 == 1 -> f(x - 7) + 1
else -> f(x + 1)
}
```
into:
```auto
fun f (x: Int): Int = f(0, x)
tailrec fun f (sum:Int, x:Int) = when {
x <= 10 -> sum+x
x % 2 == 1 -> f(sum+1, x-7)
else -> f(sum, x+1)
}
...
@Test
fun testF() {
Assert.assertEquals(10, f(10))
Assert.assertEquals(5, f(11))
Assert.assertEquals(7, f(12))
Assert.assertEquals(10, f(21))
}
```
But my question is (that’s the reason why I answered to this post); Do you plan to remove the keyword ‘tailrec’?
I mean, there are several languages in the past, they do it without the keyword. As I know even C++ optimizes these situations to an iteration, if you switch on the code optimization level O3. So I think kotlin should not need the keyword ‘tailrec’. The compiler should be able to recognize automatically these situations.
---
### Author:  [@vbezhenar](https://discuss.kotlinlang.org/u/vbezhenar)
#### Post date: [April 8, 2019, 11:43am UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/3 "2019-04-08T11:43:15Z")
tailrec is not for compiler, but for developer. Compiler translates tailrec function into a loop. Developer must be sure in that. Otherwise you might think that your function is tail-recursive, but it’s not and you’ll get unexpected stack overflow with some parameters. With tailrec compiler checks that all recursive calls are indeed tail calls and will either compiler that code into a loop or stop with error.
Think about `tailrec` as of `override`. Compiler, obviously, do not need that keyword, but developer does need it.
---
### Author:  [@code2fun](https://discuss.kotlinlang.org/u/code2fun)
#### Post date: [April 8, 2019, 12:23pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/4 "2019-04-08T12:23:22Z")
That is not a valid argument. It is not the job of the language to prevent you to do these mistakes. BTW normally it is easy to see if a function has a recursive or an iterative process.
So is there an optimization if I leave that keyword ‘tailrec’? I thought, only if I put the keyword ‘tailrec’ then the compiler optimizes it? If it is so that the compiler is optimizing it, then the discussion is redundant.
---
### Author:  [@vbezhenar](https://discuss.kotlinlang.org/u/vbezhenar)
#### Post date: [April 8, 2019, 12:26pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/5 "2019-04-08T12:26:37Z")
> [@code2fun](#):
>
> It is not the job of the language to prevent you to do these mistakes.
Of course it is the job of the language to prevent you from mistakes. The point is not about recursive functions, but about tail-recursive functions which could be optimized automatically into a loop.
---
### Author:  [@code2fun](https://discuss.kotlinlang.org/u/code2fun)
#### Post date: [April 8, 2019, 12:31pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/6 "2019-04-08T12:31:53Z")
## Tail recursive functions
Kotlin supports a style of functional programming known as [tail recursion](https://en.wikipedia.org/wiki/Tail_call). This allows some algorithms that would normally be written using loops to instead be written using a recursive function, but without the risk of stack overflow. When a function is marked with the `tailrec` modifier and meets the required form, the compiler optimises out the recursion, leaving behind a fast and efficient loop based version instead:
```auto
val eps = 1E-10 // "good enough", could be 10^-15
tailrec fun findFixPoint(x: Double = 1.0): Double =
if (Math.abs(x - Math.cos(x)) < eps) x else findFixPoint(Math.cos(x))
```
---
### Author:  [@code2fun](https://discuss.kotlinlang.org/u/code2fun)
#### Post date: [April 8, 2019, 12:35pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/7 "2019-04-08T12:35:44Z")
So, maybe I did not understand something? But I could run this code without problems! It compiles!
```auto
tailrec fun f(x: Int): Int = when {
x <= 10 -> x
x % 2 == 1 -> f(x - 7) + 1
else -> f(x + 1)
}
```
And?
---
### Author:  [@pdvrieze](https://discuss.kotlinlang.org/u/pdvrieze)
#### Post date: [April 8, 2019, 1:53pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/8 "2019-04-08T13:53:54Z")
Actually, Kotlin does not support automatic tail recursion optimization (neither does the JVM). Tail recursion for example breaks stack traces and debuggers. These are not major issues, but currently the view is that automatic tail recursion is not desirable (there was a discussion on this for Java a long time ago as well - see [this blog](https://blogs.oracle.com/jrose/tail-calls-in-the-vm) post) on the JVM. So in this case the keyword does double duty, one to opt in to the optimization, the other to ensure it is valid.
---
### Author:  [@pdvrieze](https://discuss.kotlinlang.org/u/pdvrieze)
#### Post date: [April 8, 2019, 1:56pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/9 "2019-04-08T13:56:15Z")
> [@code2fun](#):
>
> ```auto
> x % 2 == 1 -> f(x - 7) + 1
>
> ```
is not tail recursive as it needs a stack to remember the `+1`. It is valid code, but is not fully tail recursive. It is still possible to optimize the third case. Think of tail recursion as updating the parameter values and jumping back to the top of the function.
---
### Author:  [@Wasabi375](https://discuss.kotlinlang.org/u/Wasabi375)
#### Post date: [April 8, 2019, 2:03pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/10 "2019-04-08T14:03:11Z")
```kotlin
tailrec fun f(x: Int): Int = when {
x <= 10 -> x
x % 2 == 1 -> f(x - 7) + 1
else -> f(x + 1)
}
```
The compiler will indeed optimize the last case. The compiler will also generate a warning about the second case.
---
### Author:  [@code2fun](https://discuss.kotlinlang.org/u/code2fun)
#### Post date: [April 8, 2019, 2:43pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/11 "2019-04-08T14:43:29Z")
And that is not possible without the additional keyword?
---
### Author:  [@Wasabi375](https://discuss.kotlinlang.org/u/Wasabi375)
#### Post date: [April 8, 2019, 2:47pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/12 "2019-04-08T14:47:46Z")
Finding code to optimize with tailrec is possible without the keyword. As you said, languages like C++ do it.
If I remember the earlier discussion about it correctly, the reason for the keyword is following. It is easy to accidentally break tail-recursion when changing a function at a later point. The keyword is manly there, to let the programmer express that this function should be tailrecursive. It’s about being expressive. Also it allows for the warning I mentioned. If tailrecursion would be done automatically you could no longer display warnings about places where it’s not possible.
---
### Author:  [@igor\_ganapolsky](https://discuss.kotlinlang.org/u/igor_ganapolsky)
#### Post date: [January 29, 2021, 3:57pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/13 "2021-01-29T15:57:44Z")
> [@code2fun](#):
>
> It is always desireable to prefer an iterative process over a recursive one.
Why is that so?
---
### Author:  [@Wasabi375](https://discuss.kotlinlang.org/u/Wasabi375)
#### Post date: [January 29, 2021, 4:20pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/14 "2021-01-29T16:20:02Z")
Recursion is limited due to stack overflow exceptions. There is only a limited amount of data that is reserved for stack variables (which include primitives you use in functions as well as return addresses for function calls, etc). Based on the architecture of the JVM (and also most other modern native architectures) there is only a fixed size for that. You have can set the stack size for the jvm when you start a program but that size is can’t be changed after that.
If you have a recursive function you will use up that space quite quickly. While modern programming languages support recursion you will at some point run into an issue where you run out of space on the stack and get an exception and crash.
By transforming a recursive function into a iterative process you reduce the amount of stack size you need (instead of adding 1 function stack per iteration you might only need to increment a counter).
```kotlin
fun recursiveSum(numbers: List): Int {
return if(numbers.size == 1) numbers[0]
else numbers[0] + numbers.subList(1)
}
fun iterativeSum(numbers: List): Int {
var sum = 0;
for (number in numbers) {
sum += number;
}
return sum;
}
```
The iterative version will need to push 1 stack entry for each number in the list while the iterative version only needs a single stack entry.
You could fix that issue with a bigger stack size but depending on the size of the list you can always run out of space that way.
Storing data in the heap (place where object instances are stored) is much better, because the heap is only limited by how much RAM you have in your computer.
* * *
All that said recursion is nothing bad. You just have to be aware that there are limits on how deep your recursion can go before you run out of memory. `tailrec` is there to help with that. It allows you to mark a recursive function for the compiler to optimize into an iterative algorithm. That way you get an easy to read algorithm (recursion is often easier to understand) without the problems of it.
---
### Author:  [@igor\_ganapolsky](https://discuss.kotlinlang.org/u/igor_ganapolsky)
#### Post date: [January 29, 2021, 4:20pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/15 "2021-01-29T16:20:38Z")
> [@code2fun](#):
>
> `x % 2 == 1 -> f(x - 7) + 1`
You’d get a warning on this:
> Recursive call is not a tail call
---
### Author:  [@Wasabi375](https://discuss.kotlinlang.org/u/Wasabi375)
#### Post date: [January 29, 2021, 4:25pm UTC](https://discuss.kotlinlang.org/t/why-is-tailrec-a-modifier-keyword-applied-at-the-function-level/5886/16 "2021-01-29T16:25:04Z")
Yes. There are some limitations on tail-recursion. The kotlin compiler warns you when it is not possible to use.
[https://kotlinlang.org/docs/reference/functions.html#tail-recursive-functions](https://kotlinlang.org/docs/reference/functions.html#tail-recursive-functions)
> To be eligible for the `tailrec` modifier, a function must call itself as the last operation it performs. You cannot use tail recursion when there is more code after the recursive call, and you cannot use it within try/catch/finally blocks.
The issue here is the `+ 1` at the end. Still the compiler will optimize the other 2 conditions of the function. This can still be useful if you know that the part that can’t be optimized is a rare case, that way you still get some recursion but not enough to cause an issue.