Richard Feldman (Feb 27 2024 at 13:36): Richard Feldman (Feb 27 2024 at 13:36):it occurred to me that I personally always try to write recursive functions in a tail recursive way - and I do mean always; there actually are no exceptions to this I can think of (at least not since I learned that all recursive functions can be rewritten to be tail recursive)
Richard Feldman (Feb 27 2024 at 13:37):which leads me to wonder: what if we just had a warning for non-tail-recursive recursive functions?
Richard Feldman (Feb 27 2024 at 13:40):we've talked in the past about having ways to identify tail recursion, and a warning whenever it's not done seems like the simplest imaginable design for that
Richard Feldman (Feb 27 2024 at 13:41):there's no syntax or anything to learn, and you also never have to wonder if your recursive functions are tail recursive; if they aren't, you would have gotten a warning!
Richard Feldman (Feb 27 2024 at 13:42):a downside of having it as a general warning is that the fix might be nontrivial, especially if you're unfamiliar with the technique
Richard Feldman (Feb 27 2024 at 13:43):which might suggest maybe saving it for some potential future linting thing
Richard Feldman (Feb 27 2024 at 13:43):but I kinda like the idea of just trying it out and seeing how it goes in practice - maybe it's actually fine!
Richard Feldman (Feb 27 2024 at 13:44):I think we'd need a link in the warning to a write-up explaining how to rewrite any recursive function into a tail-recursive one, as a prerequisite
Richard Feldman (Feb 27 2024 at 13:44):but I'm curious what others think!
Brian Teague (Feb 27 2024 at 14:14):Absolutely, this would be very beneficial. A warning doesn't prevent the developer from testing a recursive function that hasn't been optimized to use tail recursion. I don't think I have run into a recursive function that is "non-trivial" to convert to use tail recursion. We can go even one step further making it a compile error with a "strict" option flag to enforce making functions use tail recursion.
Sky Rose (Feb 27 2024 at 14:16):It should be at most a warning, not error. The program would still work.
Sky Rose (Feb 27 2024 at 14:18):I worry that even a warning would get in the way of simple cases where it doesn't matter. "I'm recursing over a list of 3 files in this script. Why is the compiler yelling at me about performance?"
This seems like more of a linting problem than a compiler problem.
Brian Teague (Feb 27 2024 at 14:19):The strict flag would be optional. Without it, it will still just be a warning. With strict turned on, you can enforce developers to fix their warnings before building the binary. Yes, I agree with this being a linting warning.
Sky Rose (Feb 27 2024 at 14:22):Do we have plans for being able to silence lint warnings with in-line comments if you want to leave one instance unfixed and still pass the lint in CI?
Richard Feldman (Feb 27 2024 at 14:23):I plan to never enable that
Richard Feldman (Feb 27 2024 at 14:24):see https://jfmengels.net/disable-comments/
Richard Feldman (Feb 27 2024 at 14:28):Sky Rose said:
I worry that even a warning would get in the way of simple cases where it doesn't matter. "I'm recursing over a list of 3 files in this script. Why is the compiler yelling at me about performance?"
I thought about that, but in simple cases recursion is rarely needed anyway - there's usually a way to do it with walk or an even more specific collection function
Sky Rose (Feb 27 2024 at 14:34):all functions can be rewritten to be tail recursive
Is there a formulaic way to do this?
If so, can we rewrite it to be tail recursive during compilation? (I imagine not, that'd be some compiler magic.)
If not, can we expect all programmers to be able to rewrite any function to be tail recursive?
Richard Feldman (Feb 27 2024 at 14:42):in the general case I don't think it's feasible for the compiler to automate it
Richard Feldman (Feb 27 2024 at 14:43):I personally suspect that if people who can handle recursion will generally be able to handle the transformation too
Richard Feldman (Feb 27 2024 at 14:43):but I don't know! There's no data on this because as far as I know it's never been tried :big_smile:
Brendan Hansknecht (Feb 27 2024 at 15:13):I would guess that most of the time it is just noise or an annoyance for many users
Brendan Hansknecht (Feb 27 2024 at 15:13):Also, until we properly deal with mutual recursion and TCO, it wouldn't be as easy to fix in a large number of cases.
Brendan Hansknecht (Feb 27 2024 at 15:15):Oh, lastly, from some of the CPS stuff. In a number of cases, using CPS to make a function tail recursive is way slower than not being tall recursive. This is most noticable in algorithms like merge sort. I don't want to have to write a tail receive merge sort.
Brendan Hansknecht (Feb 27 2024 at 15:16):The issue is that some algorithms are best as divide and conquer. They based on splitting the input in a way that should really never build a deep enough stack for the cost to matter
Anton (Feb 27 2024 at 15:23):It seems like a compiler warning in this case would worsen the experience of beginning programmers.
Richard Feldman (Feb 27 2024 at 15:32):good points!
Agus Zubiaga (Feb 27 2024 at 15:54):Richard Feldman said:
Ironically, the only elm-review rule I have used that has disable comments is NoUnoptimizedRecursion, which checks for TCO :smile:
Norbert Hajagos (Feb 27 2024 at 17:08):We have talked about a perf tool, right? We could put this warning in there. Ppl who use that generally care about tail recursion.
Eli Dowling (Feb 29 2024 at 03:29):Hey, I talked about this a while back here: https://roc.zulipchat.com/#narrow/stream/304641-ideas/topic/Editor.20indicate.20if.20a.20function.20is.20tail.20recursive.
I definitely think an editor extension is the way to go. Then it can be toggled on and off easily and it isn't lust mess and noise.
If you wanted to have it in the cli tool I'd suggest adding a new optional category of suggestions called "hints", kind of like cargo clippy. You can run something like roc check --perf and get hints about performance issues.
I'm working on implementing it right now actually.
image.png
image.png
I found a nice edior agnostic way to display this info by adding a bunch of "hint" level diagnostics.
Interestingly I've discovered the current code that decides if a function is tail-recursive within the can crate doesn't work well and often disagrees with the IR, so I'm trying to fix that
Last updated: Jun 16 2026 at 16:19 UTC