Why is `tailrec` a modifier keyword applied at the function level?

#1

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:

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:

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

fun f(x: Int): Int = if (x > 100) @TailCall g(x / 2) else x
fun g(x: Int): Int = @TailCall f(x + 4)
2 Likes

#2

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:

tailrec fun f(x: Int): Int = when {
    x <= 10 -> x
    x % 2 == 1 -> f(x - 7) + 1
    else -> f(x + 1)
}

into:

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.

0 Likes

#3

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.

0 Likes

#4

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.

0 Likes

#5

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.

0 Likes

#6

Tail recursive functions

Kotlin supports a style of functional programming known as tail recursion. 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:

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)) &lt; eps) x else findFixPoint(Math.cos(x))
0 Likes

#7

So, maybe I did not understand something? But I could run this code without problems! It compiles!

tailrec fun f(x: Int): Int = when {
    x <= 10 -> x
    x % 2 == 1 -> f(x - 7) + 1
    else -> f(x + 1)
}

And?

0 Likes

#8

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

0 Likes

#9

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.

0 Likes

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

0 Likes

#11

And that is not possible without the additional keyword?

0 Likes

#12

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.

0 Likes