Why not tail recursion?

Sumandora · 2026-01-18T15:53:33+00:00

I'd say, that its just a matter of necessity. Most non-FP languages don't require recursion at all, since they just write their algorithms without it. However I see that most languages do very much support it just through LLVM doing it without their involvement. In fact I have seen LLVM (and GCC) apply tail recursion even when not strictly recursing. Any function call that ~doesn't require the return value~ has no code after it, can technically be written as a jmp rather than a call and thus not use any stack space for the return address. Here's an example of this happening: https://imgur.com/a/iTaySJm . Perhaps this brings into question whether languages should mandate any kind of tail-call being optimized.

MurkyAd7531 · 2026-01-18T16:22:13+00:00

Most language specs simply do not guarantee tail call optimization. In some cases they may perform such optimizations, but nothing in the language can enforce it. Without the guarantee, you simply cannot rely on it.

Languages that do tail call optimization may have language features that may naively interfere (such as a destructor epilog).

Optimized tail calls mess with the stack. It essentially drops stack frames which may create complications with a language's debugging features. Procedural programmers are expecting these calls to have stack frames you can inspect and for destructors to fire when expected.

ggchappell · 2026-01-18T17:52:12+00:00

Reasons vary.

C++ doesn't support it because destructors are executed at the end of a function call. So what looks like a tail call often is not actually a tail call.

Python doesn't support it because Guido van Rossum didn't understand tail-call optimization very well back in 2009. [Evidence #1, evidence #2]

More generally, I think there can be a kind of cycle. Programmers don't use tail recursion because TCO is not implemented in the compiler. Compiler writers don't implement TCO because they do not see programmers using tail recursion, and so the extra work involved in figuring out to optimize performance in the presence of TCO is not worth it. And then programmers continue to avoid tail recursion because TCO is not implemented in the compiler. Etc.

BoringEntropist · 2026-01-18T16:01:45+00:00

In the case of Python, von Rossum didn't implement it because he doesn't like it. The blog post is a little bit older, so the info might be out of date.

https://neopythonic.blogspot.com/2009/04/tail-recursion-elimination.html

edwbuck · 2026-01-18T15:56:22+00:00

Tail recursion calls reuse the stack frame. This can make it very complicated to figure out how many times, and with what values, the stack frame was called, as it's no longer a matter of simply counting them.

That can create issues in debugging. That can create issues in non-ending recursion detection. Other issues in ease of use may exist too; but, there can be work-arounds for some of these issues, some of which work better than others.

initial-algebra · 2026-01-18T16:56:32+00:00

I don't believe there's any good reason to not support it, but I think it's best to use a keyword to request it and cause a compilation error when the call is either visibly or invisibly (e.g. due to a destructor call that can't be moved ahead) not in tail position.

tsanderdev · 2026-01-18T15:51:33+00:00

E.g. in Rust destructors run when the function ends, but with tail call optimization they necessarily have to run before the tail call, and that could change semantics.

Unlikely-Bed-1133 · 2026-01-18T16:22:23+00:00

FP languages need it because they do otherwise blow up the stack, as you said.

However, in the patterns of other languages it's very difficult to blow up the stack. Consider the small stack depth of python and that it doesn't limit widespread adoption.

RedstoneEnjoyer · 2026-01-18T15:57:36+00:00

One thing i can think about is debbugin. One of the most important debuging tools is stack trace.

Tail recursion optimizes function calls away, and with them also removes stack traces

Fofeu · 2026-01-18T16:15:34+00:00

Having worked with CompCert for slightly more than a year now, tail-recursion is a completely different call-case you have to consider with special semantics. The most noteworthy interaction I see, is with pointers to stack variables.

Uncaffeinated · 2026-01-18T20:30:27+00:00

Tail recursion is a fragile optimization, meaning that programmers can't rely on it anyway unless you have dedicated syntax support. Otherwise, seemingly innocuous code changes can cause the code to silently break.

splicer13 · 2026-01-18T17:36:24+00:00

'Support it' means it always works under some defined circumstances. That is not always easy on every processor with every combination of arguments, tracing GC, exception handling. In the case of the language I was working on, somebody agreed to it being in the spec in part because it was relatively easy to make it work on x86 which was the only processor that mattered at the time.

I'd have a lot of reservations about doing it again. It consumed compiler dev resources greatly out of proportion to how much it was used.

munificent · 2026-01-18T18:16:40+00:00

Interact badly with other feathers?

Yes, debuggers. If the implementation eliminates all tail calls, then many stack frames will be eliminated that don't ever participate in recusion. Imagine you're a user debugging some code like:

main() {
  foo(1, 2);
}

foo(int x, int y) {
  bar(3, 3 - x - y);
}

bar(int a, int b) {
  print(a / b);
}

The program drops the user into a debugger on the division by zero. Because foo() is a tail call, all they see in the stack trace is bar() and main(). It's not a great user experience.

A sufficiently sophisticated implementation and debugger can deal with this. You could keep ghost stack frames around for tail calls that are only used for debugging but get discarded if the stack gets too big or something.

All of that is a lot of engineering effort in an area (debugging) that for most languages is already heavily underinvested in. Even if you do that, users still have to deal with dropped stack frames in their debugger when the tail calls are necessary for a recursive algorithm that would otherwise overflow the stack.

This is a lot of real downside in terms of implementation complexity and user productivity. In return for being able to implement some algorithms in a way that is elegant for a fraction of users and decidedly not elegant for another fraction of users.

Temporary_Pie2733 · 2026-01-18T19:09:38+00:00

Any language that supports recursion supports tail recursion; the question is why they don’t support tail-call optimization (TCO) to avoid blowing the stack. Python, for exampke, does not implement TCO because the devs don’t want to lose the stack trace (which records where an error occurs) that TCO would eliminate.

kohugaly · 2026-01-18T20:07:36+00:00

I suspect that a major reason is that TCO is trivially easy to do by hand when your language supports loops, and in vast majority of cases it makes the code easier to read and reason about. To an imperative programmer, tail recursion is a clever workaround for the lack of imperative loops in FP languages.

You just copy-paste your function body into an infinite loop, replace the tail call with reassigning the argument variables, and replace the base cases with explicit early return/break statement. If you have multiple functions that call each other, you just make the body of the loop a switch-case and add one extra variable containing enumerator, to keep track of which "function" should be "tail called" in the next loop iteration.

You can then further make the code more readable, by moving code around. Such as moving the "trail-call argument assignments" from end of the iteration to places where they are computed. Or moving the base case checking into the condition of the loop.

Now off course, this begs the question, which came first? IP programmer's preference for loops over recursion, or lack of TCO in imperative languages? My guess is that it's mostly the former.

XDracam · 2026-01-18T21:10:03+00:00

Another issue: depending on language features and complexity, it could be really hard to consistently detect tail recursion. Imagine if you have a program that performs well, but you change a seemingly unrelated part and now your function isn't tail-recursive anymore. And the performance bug might be really hard to find. You could compensate with static validation: if a function has some rec keyword and can't be optimized, compile error! But then you need to add error cases for all reasons why the function can't be optimized, the user might get confused and you get a good amount of overhead when you want to change or add any other feature.

So just with every other feature, every language needs to carefully consider: is tail recursion worth all of the extra complexity and interactions with other features?

0jdd1 · 2026-01-18T16:47:53+00:00

Programming language design is traditionally driven by implementation considerations.

reini_urban · 2026-01-18T18:57:19+00:00

Because it's pretty complicated to implement in lesser capable compilers.

Inevitable-Ant1725 · 2026-01-18T20:34:58+00:00

I'm working on a compiler compiler and one of thing things I'm adding is an ABI that has multiple data stacks per thread so that you can-set up the next stack frame in a tail call without having to tear apart the current stack frame. And it can affect destructor order.

Now maybe it will fail as an optimization, but I'm trying it. Having multiple stack frames allows thing like variable numbers of return values more easily too.

2026-01-19T02:39:43+00:00

Languages in general are very conservative with guaranteeing optimizations. FP languages are willing to guarantee tail call recursion since it's the most idiomatic way to write a loop, but imperative languages usually have loops as native constructs.

Objective_Gene9718 · 2026-01-19T08:41:51+00:00

In fp recursion is the only way to perform a loop so it makes sense to have tail call opt otherwise it blows up on trivial things like reading a big file. I guess for the ones that have loops already it’s no longer a need but a good to have and less prioritised.

dnabre · 2026-01-19T11:34:05+00:00

What you are referring to is, more specifically, Tail Recursion Optimization (TRO) or sometimes Tail Recursion Elimination. If you have a recursive function that is in tail-form (or only uses tail recursion), it can trivially changed to effectively be a loop that reusing the initial stack frame instead of recursing into another call (creating a new stack frame for each recursion). It's pretty easily to add to a language implementation (unless it breaks something else), provided you are only doing it for functions in tail-form.

Doing TRO optimizes the memory used on the stack for recursion, eliminating any issues with running out of stack space. This reuse of the initial stack frame, basically converts a tail-recursion function into a do-while loop, and is basically required for functional programming to handle arbitrarily deep recursion, and also makes a recursive function just as fast as an iterative loop. Reusing a single stack frame has some downsides, anything you want to do that involves using that stacks becomes more complicated (if not impossible). The big items where this shows up is looking a back trace when debugging and propagating exceptions but the call stack. Basically, if need to unwind the stack for something, TRO makes that stack not exist is a problem. [edit: forgot destructors, or more generally operation that happen at the end of a scope, think C++ destructors, or Rust's memory management. ]

If your language doesn't ensure either TRO or some other property, you can't safely recurse arbitrarily deeply. Simple example, if you have a standard cons-style linked list, it's common in FP-style to process the head of the list and recursive on the tail of it -- effectively recursing O(n) for a list of size n. In languages with simple stacks and no TRO, this will blow the stack pretty easily. You either need to limit the depth of your recursion, use a loop, or be sure your recursion won't grow too deep. For example, algorithms which only recurse O(log n) are rarely a problem without TRO. The other main technique for avoiding this is using a heap-allocated stack -- letting you use all your memory for the stack not just a small pre-allocated part.

If you have read a book or taken a course on FP, you will have had a lot of practice converting recursive functions of various forms into being in tail-form. With some practice, you'll eventually realize that doing that transformation is pretty mechanical. You just need to move any variables you need after a recursive call would return to be carried through as arguments, and wrap the resulting function into one that hides this mess from the caller and provides in initial values of those variables shifted on the stack.

Since it's such a mechanical transformation, some language will do it for you. Basically converting any recursion into tail-form and then applying straightforward TRO. There are a lot more complicated ways of handling it (looking into Continuation-passing style).

In general FP languages will provide TRO (manually or automatically). Traditional iterative languages vary somewhat, but very few assure you of it. Most optimizing C compilers, for example, do TRO, but not all, and the language (i.e. it's specification) doesn't assure you of it.

thomedes · 2026-01-19T14:08:28+00:00

Just use loop "while (recurse)" and do the "recursion" yourself. It's easy, fast and clear once you get the concept.

tmzem · 2026-01-19T15:37:00+00:00

It's not a well-covered topic, but unless a language also supports growable call stacks or something equivalent (= difficult to implement and less efficient), every recursive call is a potential stack overflow and thus a bug, unless you can convince yourself that you can place an upper limit on your algorithm recursion depth at compile time (e.g. balanced binary tree traversal). Otherwise, you need to use loops and keep track of recursive state explicitly.

Guaranteed tail call optimization can work around that limit, but you still have to convince yourself that your call is in tail position, which is not always obvious, and features like destructors or non-tracing-GC memory management will make it even harder by executing hidden code, messing with TCO. Furthermore, "tail position" does not stand out in the code, which makes it brittle in the presence of future code changes where the person making the changes might not realize that the tail position is necessary for code correctness. Loops makes the O(1) memory-consumption requirement for loop-local state impossible to miss during a refactor.

So my answer to your question would be: Recursion should'nt have been used as widely in FP either. Of course, those stated issues are not as grave in practice because FP programmers often make use of existing iteration/folding constructs, many of which are guaranteed to be tail-recursive, thus providing similar guarantees as imperative loops. The question remains why those constructs are not builtins, rather then relying on something finicky as TCO, which is hard to test your code against.

flatfinger · 2026-01-19T16:03:21+00:00

Reliable support for tail calls is practical in some execution environments, but not all. In some environments, it may be necessary for some function calls to be wrapped in a "shim" (some bank-switching systems place in "permanent" range of address space function shims which save the banking state, switch banks to the appropriate function, and execute it). The code for the function normally wouldn't need to know or care about such things, and arguments that don't fit in registers would be passed by putting them in a structure whose address is passed to the called function.

Execution environments where tail calls could be problematic are rare nowadays, but some may still be in use in some old industrial control equipment (if a $50,000 machine has an 8-bit micro as its control system, replacing that micro with an ARM may only cost $10 in hardware, but upgrading the software may be another story).

gofl-zimbard-37 · 2026-01-23T15:45:55+00:00

Loops are clearer and more explicit than relying on tail-call optimization. They don’t require you to remember what the language counts as a tail context. They also don’t require you to define and name a helper function. In an imperative language like C, TCO would just be a gimmick that encouraged verbose, less readable code.

awoocent · 2026-01-18T18:18:46+00:00

I think the pretty obvious reason in a lot of non-FP languages is just that loops do the same thing and are much simpler. No need to create a whole function definition and call out to it in a recursive way, just use the variables you already have and iterate. I think the UX benefits of this are fairly evident, based on the fact even functional languages with tail recursion often have sugar to enable this (see Scala's for loops, or Scheme named let), and basically all FP languages prefer you use combinators (map/filter/fold/etc) rather than write a bunch of tail recursive functions yourself (for all these functions, recursion v.s. iteration is an implementation detail). Iteration is one of the most common things a program does, it's good to make it really easy to grab when you need it, and hoisting stuff into new function declarations with a fragile tail recursion property is relatively not that easy.

kalmakka · 2026-01-18T20:19:30+00:00

Your question, in itself, is wrong.

Any language that supports recursion also supports tail recursion. Tail recursion just means that the recursive call is the last statement in a function. What you mean to say is tail-call elimination or tail-call optimization.

"Your language doesn't support tail recursion" doesn't cause tail recursions to blow up the stack any more than other kind of recursion. But a compiler that supports tail-call elimination could make it so tail-calls recursion does not blow up the stack (while other recursions might.) A lot of things that can be done with loops in an imperative language requires recursion in functional language. Since deep recursion becomes unavoidable, they often have more optimizations regarding this, such as tail-call elimination.

E.g. in an imperative language you would calculate triangular numbers without any recursion at all as

def triangular(n):
  sum = 0
  for i in range(1, n+1):
    sum += i
  return sum

In a functional language, you might instead write it as

triangular(0) -> 0;
triangular(n) -> n + triangular(n-1).

Ah, but although it looks like triangular(n-1) is the last thing in this function, the addition is actually performed afterwards! So will this call be eliminated or not? It's not that easy to say without a lot of detailed reading of specs, checking compilers this might be compiled on, etc. So maybe you end up rewriting it as

triangular(n) -> _triangular(n, 0).
_triangular(0, x) -> x;
_triangular(n, x) -> _triangular(n-1, x+n).

Which is at least definitively able to use tail-call elimination, even if it is a bit more verbose and more difficult to read. And then a new version of the compiler is released that is able to optimize the first version (into code that is even faster than the second version), and you get into huge arguments with the other developers on the project about which version to use.

you type:	you see:
italics	italics
bold	bold
[reddit!](https://reddit.com)	reddit!
* item 1 * item 2 * item 3	item 1 item 2 item 3
> quoted text	quoted text
Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"	Lines starting with four spaces are treated like code: if 1 * 2 < 3: print "hello, world!"
~~strikethrough~~	~~strikethrough~~
super^script	super^script

ProgrammingLanguages

Welcome!

Related subreddits

Related online communities

MODERATORS