Tail-call optimization in C is relatively recent (2025)

> In 2001 Mark Probst implemented tail-call optimization in GCC

That's me.

The motivation back then was to allow compilers that target C to assume that tail calls will be "proper". That's different from an optimization, which is usually optional, and which compilers don't guarantee.

The LWN post briefly sketches why this is hard: C allows variable-argument functions (like printf) where only the caller knows for sure how many arguments it passed, which means that only the caller can clean up the stack, unless the stack frame size is also communicated, which "normal" C calling conventions don't do. But when the callee does a proper tail call, the stack frame that returns to the callee is not the stack frame that the callee originally sent. This is explained in more detail in my thesis starting on page 16: https://hostr.flingit.run/s/proper-tail-calls.pdf

Unless the language can guarantee TCO, I don’t feel comfortable writing tail recursive code and being at the compiler’s/interpreter’s mercy.

I think the framing of TCO as an optimization has been very unfortunate.

I think Anton is replying to me in that LWN article IIRC. I personally didn't know C only had tail calls that late and learnt something new there!

On the other hand, I am pretty new to the compiler space myself, and I count early 2000s as a pretty long time ago, though again it is not that far back considering how long other language implementations had tail calls like in ML or variants since 1980-90s.

and TCO was added then removed from js! https://stackoverflow.com/a/54721813

This leads to fun stack-overflow bugs too in a lot of js code (one solution is to flatten: https://joshua.hu/javascript-infinite-tail-call-recursion-st...)

What practical patterns are enabled by TCO in C? My impression is that every tail call can written as a loop much more naturally. Tail calls are important in functional languages where you don't have mutable loop variables.

And imo they are an ugly hack even there - one of the few core constructs where its readily apparent you're not programming an abstract machine but a real, and limited computer. For example the most natural way to write factorial:

      let rec factorial n = if n <= 1 then 1 else n * factorial (n - 1)

TFA assumes pre-C89 C, I think:

> The caller could see the declaration int f();, the actual call could have n>0 arguments, and the actual function could have m≤n parameters.

Certainly if `f()` were `int f(void);` then that wouldn't be the case. But even for `int f();` C17 6.5.2.2p6 says that "If the number of arguments does not equal the number of parameters, the behavior is undefined." Near as I can tell that was made UB in C89. So TFA is a) right about K&R C, b) just wrong for pretty much all post-K&R C. C23 makes `int f();` be the same as `int f(void);`.

That calling a non-variadic function with more / fewer arguments than expected by its definition is UB is enough to make TCO possible for that function's body.

The point about K&R C is well taken though: to turn a tail call into a jump, the caller needs to know how much to pop off the stack.

For variadic if you `va_start()`, `va_arg()` as needed, then `va_end()` with no `va_copy()` left alive then you can still tail-call out correctly, otherwise you can't.

For non-variadic functions post K&R C TCO should always be possible and not UB, provided you're not triggering UB to begin with by using the incorrect number of arguments.

I recently played around with what I call "manual tail-call optimization": transform a tail call to a goto to the beginning of the function. Check it out: https://godbolt.org/z/3fY1v1oeW

  int factorial_loop_iterative(int n, int a){
    while(n > 0){
      a = a * n;
      n = n - 1;
    }
    return a;
  }
  
  int factorial_loop_recursive(int n, int a){
    if(n > 0){
      return factorial_loop_recursive(n - 1, a * n);
    }else{
      return a;
    }
  }
  
  int factorial_loop_manual(int n, int a){
  tailcall:
    if(n > 0){
      a = a * n;
      n = n - 1;
      goto tailcall;
    }else{
      return a;
    }
  }
  
  int (*factorial_loop)(int n, int a) = factorial_loop_manual;
  
  int factorial(int n){
    return factorial_loop(n, 0);
  }

GCC has had TCO since the 1980s I'm pretty sure. Since then it's been extended to work in more contexts.

>That quote is the article, and it's a little surprising that it's buried so far into the content

Is it really surprising in 2026? Today's online writing style is not primarily designed to communicate. It's designed to keep the reader 'engaged' for as long as possible. The reader's time is a resource to be extracted.

I'm absolutely not poking this author individually. It's the writing style of the net.

> In 2001 Mark Probst implemented tail-call optimization in GCC

MSVC didn't add tail-call optimisation until sometime in the 2010s, IIRC.

I distinctly remember sending a tail-recursive C++ program to someone who developed on Windows, and it crashing, in the late mid-to-late 2000s.

(2025)

> In 2001 Mark Probst implemented tail-call optimization in GCC with a separate calling convention; he lists the limitations of the then-existing tail-call optimization in GCC in section 6.4, among them: "It cannot handle indirect calls" (which would have been used in tail calls for interpreter dispatch).

Relatively recent being a quarter of century? Or at least a fifth of a century for indirect calls[1] (GCC 3.4.6 is the earliest I see on Compiler Explorer, released March 2006).

[1]: https://godbolt.org/z/vvcnn54oM

[flagged]

[flagged]