# 3 tailrec questions
**URL:** https://discuss.kotlinlang.org/t/3-tailrec-questions/3981
**Category:** Uncategorized
**Created:** [July 31, 2017, 10:36pm UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981 "2017-07-31T22:36:34Z")
**Posts on this page:** 12
**Page:** 1
### Author:  [@d\_pfeiffer](https://discuss.kotlinlang.org/u/d_pfeiffer)
#### Post date: [July 31, 2017, 10:36pm UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/1 "2017-07-31T22:36:34Z")
Consider this naïve implementation of the Ackermann-Péter function:
```
tailrec fun a( m: Int, n: Int ): Int =
if( m < 1 ) n + 1
else if( n < 1 ) a( m - 1, 1 )
else a( m - 1, a( m, n - 1 ))
```
1. Why do I need to declare `tailrec`? The compiler should easily be able to detect the calls it where it can reuse the current stack frame, instead of extending it. And this independently of whether a function calls itself or another one (possibly with a multi-hop tail recursion, which this keyword is not even capable of).
2. Why do I need to declare return type `: Int`? Only one branch terminates non-recursively. So only that one can determine the return type. Instead the compiler goes into a recursion problem.
3. This fulfills the documented requirement _a function must call itself as the last operation it performs_. It doesn’t say _must **only ever** call itself…_, and there wouldn’t seem to be a need for such a restriction. Yet it warns about the nested call: _Recursive call is not a tail call_
---
### Author:  [@elizarov](https://discuss.kotlinlang.org/u/elizarov)
#### Post date: [August 1, 2017, 2:20am UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/2 "2017-08-01T02:20:34Z")
1. Implicit `tailrec` optimization is very fragile and error-prone. People make mistakes and `tailrec` modifier is here to _explicitly_ declare programmer’s intent to define a tailrec function. You (as a programmer) declare your intent and compiler verifies it. It also serves as a helpful piece of documentation for future readers and maintainers of your code. If they accidentally break it, they’ll get caught by compiler.
2. Kotlin’s type inference is deliberately limited to allow for fast compilation. You have to declare types in Kotlin in some cases where it could have figured out type with a more complicated type inference implementation, but the more complicated implementation would have considerably slowed down compilation. That is a conscious tradeoff.
3. “Recursive call is not a tail call” is just a warning to protect programmers from making a common mistake of thinking they have a tail call, but messing something up in their code, so this is not an actual tail call. This error is hard to catch otherwise, especially in functions like Ackermann’s, where there is no chance you’ll ever catch the actual absence of tail call optimizing by performing any kind of unit test.
The common pattern for tailrec functions is to always make a recursive tail call. In the rare cases, like the Ackermann function, you want to have some non-tail calls, too. Press “Alt+ENTER” on this warning and choose a quick-fix to suppress this warning for this particular function. That serves as your (programmer’s) confirmation to compiler and future readers that you’ve intended it to be this way.
---
### Author:  [@ilya.gorbunov](https://discuss.kotlinlang.org/u/ilya.gorbunov)
#### Post date: [August 1, 2017, 2:27am UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/3 "2017-08-01T02:27:01Z")
This question also has answer why multi-hop tail recursion functions are not supported: [Kotlin: Tail recursion for mutually recursive functions - Stack Overflow](https://stackoverflow.com/questions/35714683/kotlin-tail-recursion-for-mutually-recursive-functions)
---
### Author:  [@d\_pfeiffer](https://discuss.kotlinlang.org/u/d_pfeiffer)
#### Post date: [August 1, 2017, 10:25pm UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/4 "2017-08-01T22:25:39Z")
Most C/C++ compilers have successfully done tail call optimization for years, and have been covering more edge cases over time. But of course those are fragile niche languages, which can’t compete with Kotlin 😉 The optimizations are all safe, except for some aggressive ones to cheat in benchmarks – not speaking of core dumps, which have other reasons.
It’s merely an optimization, which (apart from allowing far deeper “recursion” and allowing to implement state machines where the transitions are tail function calls – impossible in Kotlin currently without other-function call optimization) is completely transparent semantically. So it has no business to be mentioned in the code!
What in the world would be lost by checking if a function verifiably called last (with no closures remaining open, etc.) could be jumped to instead?
---
### Author:  [@d\_pfeiffer](https://discuss.kotlinlang.org/u/d_pfeiffer)
#### Post date: [August 1, 2017, 10:39pm UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/5 "2017-08-01T22:39:14Z")
This one contradicts the not-possible-on-JVM part: [compiler - Why doesn't Java have optimization for tail-recursion at all? - Software Engineering Stack Exchange](https://softwareengineering.stackexchange.com/questions/272061/why-doesnt-java-have-optimization-for-tail-recursion-at-all)
---
### Author:  [@elizarov](https://discuss.kotlinlang.org/u/elizarov)
#### Post date: [August 1, 2017, 10:45pm UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/6 "2017-08-01T22:45:02Z")
> What in the world would be lost by checking if a function verifiably called last (with no closures remaining open, etc.) could be jumped to instead?
Nothing is lost. Declare your intent with `tailrec` and it will be. I think that I’ve provided a pretty detailed explanation on why this declaration of intent is needed for safer and more readable code. Sorry, but there is nothing more I can help you with.
---
### Author:  [@ilya.gorbunov](https://discuss.kotlinlang.org/u/ilya.gorbunov)
#### Post date: [August 2, 2017, 10:04am UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/7 "2017-08-02T10:04:24Z")
> [@d\_pfeiffer](#):
>
> What in the world would be lost by checking if a function verifiably called last (with no closures remaining open, etc.) could be jumped to instead?
Do you mean jumping to the same function (recursive tail call) or jumping to another function? In case of the latter I suppose it’s impossible to compile to JVM bytecode, there’s no such bytecode instruction: [scala - What limitations does the JVM impose on tail-call optimization - Software Engineering Stack Exchange](https://softwareengineering.stackexchange.com/questions/157684/what-limitations-does-the-jvm-impose-on-tail-call-optimization)
By the way could you show, how would you implement a state machine, if you had tail call optimizations?
---
### Author:  [@d\_pfeiffer](https://discuss.kotlinlang.org/u/d_pfeiffer)
#### Post date: [August 4, 2017, 10:51pm UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/8 "2017-08-04T22:51:27Z")
I’m not sure what to think of the JVM (never having been a Java fanboy, I don’t know it). Some seem to suggest it’s possible, while others say it can’t be done, because goto only works inside one function ☹ Do they still think it’s a Java-only platform? And even Java would profit, if they did it after virtual function lookup…
Here’s a simple example of a state machine that (potentially endlessly) tail calls other functions: [Programming in Lua : 6.3](https://www.lua.org/pil/6.3.html)
A related concept, which I’m not sure is useful, but apparently people have seen a need: [Continuation-passing style - Wikipedia](https://en.wikipedia.org/wiki/Continuation-passing_style)
---
### Author:  [@d\_pfeiffer](https://discuss.kotlinlang.org/u/d_pfeiffer)
#### Post date: [August 4, 2017, 11:01pm UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/9 "2017-08-04T23:01:33Z")
You don’t explain. You just claim that it’s fragile and error-prone – quite an assertion in the face of various languages and compilers that just DTRT succesfully.
Then you go on to say that of all the possible optimizations that the compiler can perform behind the scenes, this one should be made explicit via a hinting key word in the source code.
I thought Kotlin was supposed to be elegant, but you want to make it artificially cumbersome.
But you’re right, people do make mistakes and will forget that stupid keyword. Then the program will run fine with some test data, but explode the stack with real life data, once it’s loaded to production ☹
---
### Author:  [@HughG](https://discuss.kotlinlang.org/u/HughG)
#### Post date: [August 5, 2017, 12:22pm UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/10 "2017-08-05T12:22:36Z")
I used to find it irritating in C# to be forced to declare `override`, but the first time I removed an overridden method from the base class and got surprising behaviour, I understood why it was a good thing. We’ve changed our C++ coding guidelines to require that, too - to help us avoid mistakes. I think requiring an explicit `tailrec` is a good idea for the same reason.
---
### Author:  [@nanodeath](https://discuss.kotlinlang.org/u/nanodeath)
#### Post date: [August 8, 2017, 4:45pm UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/11 "2017-08-08T16:45:06Z")
Kotlin is elegant because it capture’s programmer intent succinctly, not because it guesses programmer intent.
One of the problems with Java and C# is a lack of transparency – it’s often hard to tell if a section of code will actually be performant or not because of the JITing behavior of the JVM. Escape analysis and method inlining (among numerous other JIT optimizations), while good for performance, make it hard to reason about what the program is actually going to do at runtime.
Admittedly, since Kotlin runs on the JVM, we still have that problem, but we’re given additional tools to add some determinism. `inline`, for instance, forces that method to be inlined at compile time, instead of hoping it’ll be inlined at runtime. That’s quite nice. It’s more verbose, but enables the developer to specify exactly what they want. And it’s just one keyword. `tailrec` is another.
The problem with tail recursive calls is that it’s way more than a matter of performance. (I’m not really familiar with the algorithm you chose for your example, so I’ll use fibonacci instead). If you implement a naive fibonacci-calculating function recursively, you’ll probably want to use `tailrec`. Then you can say `fibonacci(10)`, or `fibonacci(100)`, and it’ll still work. The latter might be slow, but it’ll work. Now, if tail recursion was _implicit_…well, it might still work. But what if you make an “optimization” to your algorithm? Try to make it a bit faster, but still **_hoping_ that Kotlin/JVM will use tail recursion**. If you’re wrong, the program will **crash** with StackOverflowError randomly for certain inputs, inputs you might not even be testing for! It introduces a “denial of service” vector to your function. On the other hand, if you knew you _had_ to have tail recursion for this function (because you wrote it a certain way and know the stack might otherwise get too deep), then the `tailrec` keyword will ensure you won’t hit that dreaded StackOverflowError ever again. Anything that acts as guard rails to keep our software running smoothly I’m quite in favor of, even if it means an extra keyword.
---
### Author:  [@andrey\_skoskin](https://discuss.kotlinlang.org/u/andrey_skoskin)
#### Post date: [May 25, 2018, 9:42pm UTC](https://discuss.kotlinlang.org/t/3-tailrec-questions/3981/12 "2018-05-25T21:42:54Z")
Could You please provide some examples of “very fragile and error-prone” code with tail recursion? I never saw any special keyword for tail recursive functions in functional languages except for JVM-based languages, and AFAIR it is only because of JVM does not support TCO by itself. Even not-so-functional Common Lisp has no macro or special form for tail recursive functions although some implementations (like SBCL e.g.) can do TCO while it is not specified by CL Standard.