Why this matters
Every recursive call uses a new block of memory on the call stack. That block, called a frame, holds the function's parameters and the place to return to. A recursion that goes a million calls deep needs a million blocks. With a fixed-size stack, the program crashes long before that. The previous lesson showed this with a flood fill on a large grid.
Some recursive calls do not need a new block at all. If the function's last step is the recursive call, and nothing is left to do when that call returns, the current block is no longer needed. A compiler can reuse it, or turn the call into a jump back to the top of the function. This is called tail call optimisation. A tail call is a call made in tail position, which means the call is the last thing the function does before it returns.
The rule is simple to state, but it is not guaranteed in every language. C++ compilers may do it when optimisation is turned on. Java does not do it for ordinary methods. A function that works in one language can crash with a stack overflow in the other. This lesson shows the rule, the compiler's behaviour, and how to write the loop yourself so the result does not depend on the compiler.
What tail position means
A call is in tail position when the function returns the call's result directly, with no other work after it. Here are some examples.
int a(int n) { return a(n - 1); } // tail: the result is returned as it is
int b(int n) { return 1 + b(n - 1); } // not tail: 1 is added after the call returns
int c(int n) { return n * c(n - 1); } // not tail: n is multiplied after the call returns
void d(int n) { d(n - 1); } // tail: nothing happens after the call
void e(int n) { d(n - 1); cout << n; } // not tail: a print happens after the callThese examples come from the plain rule. A call is in tail position when the function's work is finished by the time the call starts. Adding a number, multiplying, printing, or storing a result all count as work after the call. In e, the call to d returns and then cout << n runs, so e still needs its own frame after the call.
Two more examples show branches. A call inside an if can still be a tail call, as long as each branch returns the call directly.
bool isEvenTail(int n) {
if (n == 0) return true;
return isOddTail(n - 1); // tail call
}The if is not the problem. Each branch either returns a value without a call, or returns the call directly.
Following the stack by hand
Here are two ways to add the numbers from 3 down to 1. The first returns the sum on the way back. The second carries the total forward in a parameter.
int sumPlain(int n) {
if (n == 0) return 0;
return n + sumPlain(n - 1);
}
int sumTail(int n, int total) {
if (n == 0) return total;
return sumTail(n - 1, total + n);
}Trace sumPlain(3) line by line. Each indented line is a call that is still waiting on the stack.
sumPlain(3) waits to add 3
sumPlain(2) waits to add 2
sumPlain(1) waits to add 1
sumPlain(0) returns 0
sumPlain(1) returns 1 + 0 = 1
sumPlain(2) returns 2 + 1 = 3
sumPlain(3) returns 3 + 3 = 6Three calls are waiting at the deepest point, and each one holds its number until the answer comes back.
Now trace sumTail(3, 0).
sumTail(3, 0) calls sumTail(2, 3) and has nothing left to do
sumTail(2, 3) calls sumTail(1, 5) and has nothing left to do
sumTail(1, 5) calls sumTail(0, 6) and has nothing left to do
sumTail(0, 6) returns 6Each call has nothing to do after its call starts, so the frame of sumTail(3, 0) is not needed once it has made the call to sumTail(2, 3). A compiler can reuse that frame for the next call. The first trace cannot be handled this way, because each call still has an addition waiting when its inner call returns. That is the difference the rest of this lesson is about.
Worked example 1: the same function, three ways
Take the factorial of a number. The factorial of 5 is 5 times 4 times 3 times 2 times 1, which is 120. The plain recursive version multiplies after each call returns, so it is not a tail call.
The trick is to carry the running product into the call. The product is passed as an extra parameter called acc, short for accumulator. Then the call is the last thing the function does, and it is a tail call. The loop version does the same steps with a while loop.
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
// Not a tail call: after the recursive call returns, n is still multiplied in.
unsigned long long factPlain(unsigned long long n) {
if (n <= 1) return 1;
return n * factPlain(n - 1);
}
// A tail call: the recursive call is the last thing that happens.
// The running product is carried in `acc` instead of being multiplied on the way back.
unsigned long long factAcc(unsigned long long n, unsigned long long acc) {
if (n <= 1) return acc;
return factAcc(n - 1, acc * n);
}
// The same function written as a loop.
unsigned long long factLoop(unsigned long long n) {
unsigned long long acc = 1;
while (n > 1) {
acc *= n;
n -= 1;
}
return acc;
}
int main(int argc, char** argv) {
unsigned long long n = argc > 1 ? strtoull(argv[1], nullptr, 10) : 10;
if (argc > 2 && string(argv[2]) == "plain") {
cout << "plain: " << factPlain(n) << "\n";
} else if (argc > 2 && string(argv[2]) == "acc") {
cout << "acc: " << factAcc(n, 1) << "\n";
} else {
cout << "loop: " << factLoop(n) << "\n";
}
}The program takes the number and the version name from the command line. Compile it twice, once with no optimisation and once with -O2, which asks the compiler to make the code faster and enables tail call optimisation.
g++ -std=c++20 -Wall -O0 -o tail1_O0 tail1.cpp
g++ -std=c++20 -Wall -O2 -o tail1_O2 tail1.cppWith 20 as the input, all three versions agree.
./tail1_O0 20 plain
./tail1_O0 20 acc
./tail1_O0 20plain: 2432902008176640000
acc: 2432902008176640000
loop: 2432902008176640000Now try a very large input, 10,000,000, with the unoptimised build.
./tail1_O0 10000000 acc
./tail1_O0 10000000 plainBoth runs stop with exit code 139, which means a segmentation fault. The program ran out of stack, because at -O0 every call keeps its own frame, and ten million frames do not fit. The accumulator version did not help here. At this optimisation level, the compiler does not turn the tail call into a loop, so the tail position alone is not enough.
Now try the optimised build.
./tail1_O2 10000000 acc
./tail1_O2 10000000 plain
./tail1_O2 10000000All three print 0 and exit with code 0. The printed value is 0 because the product of ten million numbers is far larger than 64 bits. It wraps around, and with this many factors of 2, the low 64 bits end up as zero. The important part is the exit code. Even the plain version, which is not a tail call, ran without a crash. The compiler at -O2 turned both recursive versions into loops. To see what it did, compile the two functions with the names kept readable.
extern "C" __attribute__((noinline)) unsigned long long fact_plain(unsigned long long n) {
if (n <= 1) return 1;
return n * fact_plain(n - 1);
}
extern "C" __attribute__((noinline)) unsigned long long fact_acc(unsigned long long n, unsigned long long acc) {
if (n <= 1) return acc;
return fact_acc(n - 1, acc * n);
}g++ -std=c++20 -Wall -O2 -S -o tail_asm.s tail_asm.cppThe assembly (the machine instructions the compiler writes, in text form) for fact_plain contains a loop with a conditional jump back to an earlier label, and no call instruction. The same is true for fact_acc. So for this pair of functions, the compiler replaced the recursion with a loop on its own. This is a compiler choice, not a rule of the language. The lesson is that you cannot count on the compiler doing it, and a rewrite by hand is the only way to be sure.
Worked example 2: a tail call that becomes a jump
Calls to a different function in tail position are easier for the compiler to turn into a jump. This is called a sibling call. Here are two functions that call each other. The number is even if the number one less is odd, and the number is odd if the number one less is even. Each function ends with a call to the other.
extern "C" bool is_odd(unsigned long long n);
extern "C" __attribute__((noinline)) bool is_even(unsigned long long n) {
if (n == 0) return true;
return is_odd(n - 1);
}
extern "C" __attribute__((noinline)) bool is_odd(unsigned long long n) {
if (n == 0) return false;
return is_even(n - 1);
}The noinline attribute tells the compiler not to copy the functions into their callers. That keeps the two functions separate, so the compiler has to choose how to make the call from one to the other. The main program is in a second file.
#include <cstdlib>
#include <iostream>
extern "C" bool is_even(unsigned long long n);
int main(int argc, char** argv) {
unsigned long long n = argc > 1 ? strtoull(argv[1], nullptr, 10) : 10;
std::cout << n << " is even: " << (is_even(n) ? "yes" : "no") << "\n";
}Build both versions and run them with ten million as the input.
g++ -std=c++20 -Wall -O0 -o tail3_O0 tail3.cpp main3.cpp
g++ -std=c++20 -Wall -O2 -o tail3_O2 tail3.cpp main3.cpp
./tail3_O0 1000000
./tail3_O0 10000000
./tail3_O2 10000000
./tail3_O2 10000001The output on the machine used for this lesson:
(no output, exit code 139)
(no output, exit code 139)
10000000 is even: yes
10000001 is even: noAt -O0 the program runs out of stack at one million calls. At -O2 it handles ten million, and the answer is right. To see why, look at the assembly for is_even, generated with -O2. The listing drops the assembler directives, which are the lines that start with a dot, so the real output is longer.
g++ -std=c++20 -O2 -S -o tail3.s tail3.cppis_even:
endbr64
testq %rdi, %rdi
jne .L7
movl $1, %eax
ret
.L7:
subq $1, %rdi
jmp is_oddThe last instruction is jmp is_odd. A jmp moves the program to another place without making a new frame. The call to is_odd has become a jump, so the stack does not grow. The function is_odd does the same with a jump to is_even. Each call replaces the one before it.
The compiler did this without being asked, but only because the build was optimised. The source code is the same in both builds.
Worked example 3: rewriting by hand
You can remove the doubt by writing the loop yourself. The steps are the same every time.
- Find the parameters that change from one call to the next. In the factorial example, these are
nandacc. - Put the starting values into local variables before the loop.
- Replace the recursive call with new values for those variables.
- Replace the base case with the loop's end condition, and return the variables' final value.
The first example is greatest common divisor, the largest number that divides two numbers evenly. The rule is: if b is 0, the answer is a. Otherwise, the answer is the gcd of b and the remainder of a divided by b. The recursive call is in tail position.
The second example walks a vector. The running total and the index are the parameters that change.
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
// Tail call: the last step is the recursive call, with the new pair passed in.
int gcdRec(int a, int b) {
if (b == 0) return a;
return gcdRec(b, a % b);
}
// The same steps as a loop: the parameters are reassigned instead of passed on.
int gcdLoop(int a, int b) {
while (b != 0) {
int rest = a % b;
a = b;
b = rest;
}
return a;
}
// Tail call that walks a vector: the index and the running total are passed along.
long long sumRec(const vector<int>& v, size_t i, long long total) {
if (i == v.size()) return total;
return sumRec(v, i + 1, total + v[i]);
}
// The same walk as a loop.
long long sumLoop(const vector<int>& v) {
long long total = 0;
for (size_t i = 0; i < v.size(); ++i) total += v[i];
return total;
}
int main() {
cout << "gcdRec(1071, 462) = " << gcdRec(1071, 462) << "\n";
cout << "gcdLoop(1071, 462) = " << gcdLoop(1071, 462) << "\n";
vector<int> v = {4, 8, 15, 16, 23, 42};
cout << "sumRec = " << sumRec(v, 0, 0) << "\n";
cout << "sumLoop = " << sumLoop(v) << "\n";
vector<int> big(1000000, 1);
cout << "sumLoop big = " << sumLoop(big) << "\n";
cout << "sumRec big = " << sumRec(big, 0, 0) << "\n";
}Compile with -O2 and run it.
g++ -std=c++20 -Wall -O2 -o tail4_O2 tail4.cpp
./tail4_O2gcdRec(1071, 462) = 21
gcdLoop(1071, 462) = 21
sumRec = 108
sumLoop = 108
sumLoop big = 1000000
sumRec big = 1000000The loop versions are the ones to trust. The recursive sumRec with a million elements works here only because the build is optimised. The same program built with -O0 stopped with exit code 139 on the same million-element call, before it printed anything. When the output goes to a file or a pipe, it stays in the buffer until the program ends, so the crash shows no lines.
The loop rewrite does not change the answer. The steps happen in the same order, and the variables hold the same values that the recursion would pass along. That is the test to use when you rewrite any function: the loop should give the same result on the same inputs.
Java and tail calls
Java does not remove tail calls for ordinary methods. The Java Language Specification and the JVM specification do not require it, and the usual Java runtime, HotSpot, does not do it in general. The main reasons given are that removing a frame would change stack traces, which Java prints when an exception happens, and that some library code, such as security checks, looks at the chain of callers. Removing the frame would change what those checks see.
Here is a Java method that counts down with a tail call.
public class Countdown {
static long countDown(long n) {
if (n == 0) return 0;
return countDown(n - 1);
}
public static void main(String[] args) {
long n = Long.parseLong(args[0]);
System.out.println("result: " + countDown(n));
}
}Compile it and run it with two inputs. The Java version used here is OpenJDK 25.
javac -d . Countdown.java
java -cp . Countdown 10000
java -cp . Countdown 1000000result: 0
Exception in thread "main" java.lang.StackOverflowError
at Countdown.countDown(Countdown.java:4)
at Countdown.countDown(Countdown.java:4)
at Countdown.countDown(Countdown.java:4)The first run works. The second run prints a StackOverflowError and stops. The stack trace continues with the same line many times. Java prints only the first 1024 frames, so the output is 1025 lines long. This happens even though the call is in tail position, because Java keeps each frame. The tail position is not enough in Java.
The loop version of the same method does not recurse at all.
public class Loop {
static long countDown(long n) {
while (n != 0) n = n - 1;
return 0;
}
public static void main(String[] args) {
long n = Long.parseLong(args[0]);
System.out.println("result: " + countDown(n));
}
}javac -d . Loop.java
java -cp . Loop 1000000result: 0Other languages on the JVM add the feature on purpose. Kotlin has a tailrec modifier that makes the compiler turn a tail-recursive function into a loop. Scala has an annotation called @tailrec, and the compiler rejects the function if it cannot make the change. In Java, you rewrite the function as a loop.
Common mistakes
Adding work after the call. The function looks recursive and simple, but the multiplication or addition after the call means the call is not in tail position.
int countUp(int n) {
if (n == 0) return 0;
return 1 + countUp(n - 1);
}Adding an accumulator fixes it. The new version passes the count down and returns it when the base case is reached. Starting the accumulator at the wrong value gives the wrong answer with no error message. If acc starts at 0 in the factorial, every product becomes 0, and factAcc(5, 0) returns 0. The start value must be 1 for a product.
Relying on optimisation. A function that works at -O2 can crash at -O0. The tail3 program ran ten million calls at -O2 and crashed at one million with -O0. Plain g++ builds without -O2, and many debugging setups do the same. Code that depends on the compiler's choice can pass a test on one machine and crash on another. The loop rewrite is the safe choice.
Expecting Java to remove the call. The Countdown program has the call in tail position and still overflows at one million calls. A Java developer who uses tail-recursive style for long inputs will hit this error. Write the loop.
Forgetting to update a variable in the loop. When you turn a recursive call into a loop, every parameter that changes must be reassigned. In factLoop, leaving out n -= 1 makes the loop run forever, because n never reaches 1. A missing update is a silent error: the program hangs, and it does not print anything.
Practice
Exercise 1. For each function below, say whether the marked call is in tail position.
int a(int n) { if (n == 0) return 0; return 1 + a(n - 1); }
bool b(int n) { if (n == 0) return true; return b(n - 2); }
void c(int n) { if (n == 0) return; c(n - 1); cout << n; }
int d(int n) { if (n == 0) return 0; if (n % 2) return d(n - 1); return d(n / 2); }Show the answer
In a, the call is not in tail position, because 1 is added after it returns. In b, the call is in tail position, because it is returned directly. In c, the call is not in tail position, because cout << n runs after it. In d, both calls are in tail position, because each one is returned directly from its branch.
Exercise 2. Write a tail-recursive version and a loop version of countDigits, which returns how many digits an unsigned number has. Zero has one digit.
Show the answer
The accumulator starts at 1, and each step divides the number by 10 and adds 1 to the count. The loop does the same work with a variable for the count. Both return 1 for 0 and 9, 2 for 10, and 5 for 12345.
int countDigitsAcc(unsigned n, int count) {
if (n < 10) return count;
return countDigitsAcc(n / 10, count + 1);
}
int countDigitsLoop(unsigned n) {
int count = 1;
while (n >= 10) {
n /= 10;
++count;
}
return count;
}The program prints 0: acc 1 loop 1, 10: acc 2 loop 2, 12345: acc 5 loop 5, and 1000000: acc 7 loop 7.
Exercise 3. Write the loop version of this recursive binary search. The function returns the index of target in a sorted vector, or -1 when it is not there. Both calls at the end are in tail position.
int searchRec(const vector<int>& v, int target, int lo, int hi) {
if (lo > hi) return -1;
int mid = lo + (hi - lo) / 2;
if (v[mid] == target) return mid;
if (v[mid] < target) return searchRec(v, target, mid + 1, hi);
return searchRec(v, target, lo, mid - 1);
}Show the answer
The parameters lo and hi change on each call, so they become local variables. The loop runs while lo is not past hi.
int searchLoop(const vector<int>& v, int target) {
int lo = 0;
int hi = (int)v.size() - 1;
while (lo <= hi) {
int mid = lo + (hi - lo) / 2;
if (v[mid] == target) return mid;
if (v[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}On the sorted list 2, 5, 8, 12, 16, 23, 38, 56, 72, 91, the recursive and loop versions both return 5 for 23, 0 for 2, 9 for 91, and -1 for 50.
Exercise 4. The Fibonacci function int fib(int n) { if (n < 2) return n; return fib(n - 1) + fib(n - 2); } makes two recursive calls. Explain why neither of them is in tail position.
Show the answer
The first call, fib(n - 1), returns a value that the function must hold while it makes the second call, so the function still has work to do after the first call finishes. The second call, fib(n - 2), is followed by the addition. Neither call is the last step, so neither can be turned into a jump. Fibonacci can still be written as a loop that keeps the last two values, but that loop is a rewrite of the algorithm, not of the calls.
Exercise 5. Explain why tail3 at -O2 handles ten million calls while the same code at -O0 does not handle one million.
Show the answer
At -O2, the compiler replaces each call in tail position with a jump. The jump reuses the current frame, so the stack does not grow, and ten million steps need no more memory than one step. At -O0, the compiler keeps each call as a real call with its own frame. A million frames are more than the 8 MB stack can hold on this machine, so the program stops with exit code 139.
Summary
- A call is in tail position when nothing happens after it returns, so the function's result is the call's result.
- A compiler at
-O2may turn a tail call into a jump or a loop, but a-O0build keeps every frame, so the same code can crash. - Java keeps every frame, so a tail-recursive method still overflows the stack on long inputs.
- To rewrite a tail-recursive function, make each changing parameter a local variable, reassign it in a loop, and return the final value.
- Check a rewrite by running both versions on the same inputs and comparing the results.