jambit Toilet Paper #93

Tail Call Elimination

Problem: Many Function Calls in Functional Programming

Functional programming loves functions and recursions in all varieties.

<fud>But these many small function calls are very expensive, aren’t they? And what if my stack overflows during a recursion?</fud>

Solution: Tail Call Elimination

Various compilers/interpreters or languages ​​(Scheme requires this from the interpreter) provide tail call elimination, e.g. Lisp, Scheme, Lua, Erlang, Elixir, C/C ++ and to a certain extent also Scala and Kotlin. However, you must adapt your code to trigger this feature. What is it and how does it work?

Example for a Recursion With Tail Calls

Let's have a closer look at a trivial example of a recursive function:

a) "Naive" recursion
int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
b) Recursion with tail calls
int f_hlp(int n, int acc) {
    if (n == 0) return acc;
    return f_hlp(n-1, acc*n);
 int factorial_2(int n) {
    return f_hlp(n, 1);

Version a) is quite close to the mathematical definition and would probably occur spontaneously to most people. Version b) seems to be unnecessarily complicated and needs a helper function. So why using it?

The small difference is that the functions in b) end with a function call (the “tail call”). Its result is not processed any further but simply forwarded to the caller (in (a) it is used for a subsequent multiplication). This ultimately means that no new stack frame needs to be created, but the existing one can simply be overwritten. The call degenerates to a goto; the return address is already on the stack.

The compiler transforms the recursion into a loop, so that we don't have to misshape our code with ugly for loops. At runtime, the code acts like a loop (in terms of speed and stack usage) but remains slim and readable.

Further Aspects

  • Although recursion is the standard example here, it is called "tail call elimination" and not "tail recursion elimination" -- several different functions can be involved
  • When debugging, you should keep in mind that the stack trace is very shortened and can seem strange or useless.
  • If your "language of choice" doesn't support this feature, you can:
    1. ignore it and use recursion anyway
    2. convert the recursion into a loop (which is usually possible … except for Ackermann function and similar)
    3. use a "trampoline" (spoiler: heavy going, sloooow)
  • I leave it as a practice up to the reader to implement b) with a fold
  • By the way, this topic was already covered in 1977 by Guy Steele in one of his “Lambda Papers“ ("The Ultimate goto"): http://dspace.mit.edu/bitstream/handle/1721.1/5753/AIM-443.pdf
  • Outtakes: When I wanted to test b) with gcc, I wrote a main, which only consisted of printf("5! = %i\n", factorial_2(5)). I was quite surprised when the call was completely gone in the assembler code and the “stupid compiler” simply pushed 120 to edx and called printf with it.
  • Outtakes 2: So I just threw out the main and compiled both functions: gcc turns both versions a) and b) into exactly the same loop (three opcodes long). My whole example is kind of pointless. These damn low-level languages …



Hannes Lerchl / Senior Software Architect / Business Division New Business

Download Toilet Paper #93: Tail Call Elimination (pdf)

Tail Call Elimination in funktionaler Programmierung

Cookie Settings

This website uses cookies to personalize content and ads, provide social media features, and analyze website traffic. In addition, information about your use of the website is shared with social media, advertising, and analytics partners. These partners may merge the information with other data that you have provided to them or that they have collected from you using the services.

For more information, please refer to our privacy policy. There you can also change your cookie settings later on.

contact icon

Contact us now