Tail recursion in gcc/g++

by

With -O2 enabled, gcc will perform tail call optimization, if possible. Now, the question is: When is it possible?

It is possible to eliminate a single recursive call whenever the recursive call happens either immediately before or inside the (single) return statement, so there are no observable side effects afterwards other than possibly returning a different value. This includes returning expressions involving the ternary operator.
Note that even if there are several recursive calls in the return expression (such as in the well-known fibonacci example: return (n==1) ? 1 : fib(n-1)+fib(n-2);), tail call recursion is still applied, but only ever to the last recursive call.

As an obvious special case, if the compiler can prove that the recursive function (and its arguments) qualifies as constant expression, it can (up to a configurable maximum recursion depth, by default 500) eliminate not only the tail call, but the entire execution of the function. This is something GCC does routinely and quite reliably at -O2, which even includes calls to certain library functions such as strlen on literals.

More Related Contents:

  1. Why doesn’t GCC optimize a*a*a*a*a*a to (a*a*a)*(a*a*a)?
  2. How to see which flags -march=native will activate?
  3. How do I check if gcc is performing tail-recursion optimization?
  4. Understanding recursion [closed]
  5. Why doesn’t gcc resolve _mm256_loadu_pd as single vmovupd?
  6. Tail recursion in C++
  7. How to apply -fvisibility option to symbols in static libraries?
  8. How to install GCC piece by piece with GMP, MPFR, MPC, ELF, without shared libraries?
  9. Gcc error: gcc: error trying to exec ‘cc1’: execvp: No such file or directory
  10. How do I force gcc to inline a function?
  11. What’s the difference between gcc and g++/gcc-c++?
  12. Exec format error 32-bit executable Windows Subsystem for Linux?
  13. How do I run the GCC preprocessor to get the code after macros like #define are expanded?
  14. GCC(/Clang): Merging functions with identical instructions (COMDAT folding)
  15. Why does GCC generate 15-20% faster code if I optimize for size instead of speed?
  16. How to turn off gcc compiler optimization to enable buffer overflow
  17. ARM compilation error, VFP registers used by executable, not object file
  18. Can CMake use g++ to compile C files?
  19. Why does the enhanced GCC 6 optimizer break practical C++ code?
  20. How do I force cmake to include “-pthread” option during compilation?
  21. How do I set up CLion to compile and run?
  22. Executable file generated using GCC under cygwin
  23. Disable specific warnings in GCC [duplicate]
  24. CFLAGS, CCFLAGS, CXXFLAGS – what exactly do these variables control?
  25. CMake: The C Compiler is not able to compile a simple test program
  26. “undefined reference” errors when trying to use address sanitizer with GCC
  27. Undefined reference to `omp_get_max_threads_’
  28. Compiler changes printf to puts
  29. Fast Division on GCC/ARM
  30. define a program section in C code (GCC)

Leave a Comment