Which, if any, C++ compilers do tail-recursion optimization?

by

All current mainstream compilers perform tail call optimisation fairly well (and have done for more than a decade), even for mutually recursive calls such as:

int bar(int, int);

int foo(int n, int acc) {
    return (n == 0) ? acc : bar(n - 1, acc + 2);
}

int bar(int n, int acc) {
    return (n == 0) ? acc : foo(n - 1, acc + 1);
}

Letting the compiler do the optimisation is straightforward: Just switch on optimisation for speed:

  • For MSVC, use /O2 or /Ox.
  • For GCC, Clang and ICC, use -O3

An easy way to check if the compiler did the optimisation is to perform a call that would otherwise result in a stack overflow — or looking at the assembly output.

As an interesting historical note, tail call optimisation for C was added to the GCC in the course of a diploma thesis by Mark Probst. The thesis describes some interesting caveats in the implementation. It’s worth reading.

More Related Contents:

  1. Optimization code for a debug function (c++11 with templates) [closed]
  2. What are copy elision and return value optimization?
  3. Why does C++ code for testing the Collatz conjecture run faster than hand-written assembly?
  4. Meaning of acronym SSO in the context of std::string
  5. Position of least significant bit that is set
  6. Modular arithmetics and NTT (finite field DFT) optimizations
  7. What are the mechanics of short string optimization in libc++?
  8. Why is transposing a matrix of 512×512 much slower than transposing a matrix of 513×513?
  9. gcc optimization flag -O3 makes code slower than -O2
  10. Constants and compiler optimization in C++
  11. Fastest way to get IPv4 address from string
  12. while (1) Vs. for (;;) Is there a speed difference?
  13. GCC C++ “Hello World” program -> .exe is 500kb big when compiled on Windows. How can I reduce its size?
  14. C/C++: Optimization of pointers to string constants
  15. Which is better option to use for dividing an integer number by 2?
  16. Why does Clang optimize away x * 1.0 but NOT x + 0.0?
  17. When do compilers inline C++ code?
  18. Fastest implementation of sine, cosine and square root in C++ (doesn’t need to be much accurate)
  19. Should I unify two similar kernels with an ‘if’ statement, risking performance loss?
  20. Get sum of values stored in __m256d with SSE/AVX
  21. how to optimize matrix multiplication (matmul) code to run fast on a single processor core
  22. Is a logical right shift by a power of 2 faster in AVR?
  23. Branchless code that maps zero, negative, and positive to 0, 1, 2
  24. Is it legal for a C++ optimizer to reorder calls to clock()?
  25. Optimizing member variable order in C++
  26. Which is faster/preferred: memset or for loop to zero out an array of doubles?
  27. How can adding code to a loop make it faster?
  28. Fastest way to produce a mask with n ones starting at position i
  29. VS: unexpected optimization behavior with _BitScanReverse64 intrinsic
  30. std::array with aggregate initialization on g++ generates huge code

Leave a Comment