15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
Tail recursion is recursion where the recursive call is the last action of the function, so nothing waits on its result. An accumulator parameter carries the partial answer, as in sumTail(n - 1, acc + n). Time is O(n). Stack space is O(1) only if the runtime does tail-call optimization, and Python, Java and V8 JavaScript do not.
| Tail position | The call is the final action, with no arithmetic left after it returns |
|---|---|
| Non-tail form | return n + sumTo(n - 1), the addition waits |
| Tail form | return sumTail(n - 1, acc + n), the addition happens first |
| Time | O(n), n + 1 calls |
| Stack space | O(n) without tail-call optimization, O(1) with it |
The lesson assumes you can already identify:
We will use nonnegative integers only.
A recursive call is in tail position when it is the final action performed by its caller. After that call returns, the caller has no arithmetic or other work left to do.
Compare these two shapes:
Non-tail recursion: return n + sumTo(n - 1)
The addition waits until the recursive call returns.
Tail recursion: return sumTail(n - 1, acc + n)
The addition happens before the call. The caller returns the recursive result directly.
An accumulator is a parameter that carries partial progress into the next call.
Start with the helper call:
1sumTail(3, 0)The helper contract will be:
sumTail(n, acc)returnsaccplus the sum of integers from1throughn.
So the expected result is:
10 + 1 + 2 + 3 = 6The two values have separate jobs:
| Parameter | Meaning at the start |
|---|---|
n = 3 | Numbers 1 through 3 still need to be included. |
acc = 0 | The partial sum already collected. |
Add 3 to acc before the recursive call, then reduce the remaining range.
1(3, 0) → (2, 3)Trace the original call one frame at a time.
| Active call | Check | Next action | New call |
|---|---|---|---|
sumTail(3, 0) | n is not 0 | Add 3 into acc: 0 + 3 = 3 | sumTail(2, 3) |
sumTail(2, 3) | n is not 0 | Add 2 into acc: 3 + 2 = 5 | sumTail(1, 5) |
sumTail(1, 5) | n is not 0 | Add 1 into acc: 5 + 1 = 6 | sumTail(0, 6) |
sumTail(0, 6) | n is 0 | Nothing remains to add | Return 6 |
Read the calls in order:
Each sumTail call adds n into acc before calling: (3, 0), (2, 3), (1, 5), (0, 6). The base case returns 6 and every caller passes that same 6 back with no addition.
At every non-base call, the recursive call is the final action:
1return sumTail(n - 1, acc + n)No expression such as n + waits after the call. The source code is tail recursive.
When sumTail(0, 6) returns 6, each earlier caller returns that same value. No caller performs an addition.
Look at the first state:
1sumTail(3, 0)The accumulator plus the numbers still remaining is:
1acc + (1 + 2 + 3)
2= 0 + 6
3= 6After one call, the state is:
1sumTail(2, 3)Now:
1acc + (1 + 2)
2= 3 + 3
3= 6The required answer has not changed. The call moved 3 from the remaining work into acc.
The invariant is:
For every valid call
sumTail(k, acc),accplus the sum of integers from1throughkequals the final required sum. The recursive update preserves this total.
For the next state:
1sumTail(1, 5)we still have:
15 + (1) = 6For the base state:
1sumTail(0, 6)there are no integers left to add:
16 + 0 = 6The accumulator already holds the answer.
The helper keeps two pieces of state:
n: the largest number not yet included.acc: the total already included.The helper must satisfy this contract:
Input: a nonnegative integer
nand an accumulatoracc.
Return:acc + 1 + 2 + ... + n.
Mutation: does not mutate any input or external state.
Start with the stopping condition.
If n is 0, no values remain from 1 through n. The contract requires the result to be exactly acc.
1sumTail(0, acc) returns accFor n > 0, include n in the accumulator:
1new accumulator = acc + nThen reduce the remaining range:
1new n = n - 1The recursive call is:
1sumTail(n - 1, acc + n)The public wrapper begins with no values accumulated:
1sumToTail(n) = sumTail(n, 0)The wrapper has the same result as a usual sumTo(n) definition for valid nonnegative n.
1FUNCTION sumTail(n, acc) RETURNS integer
2 INPUT:
3 n : nonnegative integer
4 acc : integer representing the sum already accumulated
5 RETURNS:
6 acc + the sum of all integers from 1 through n
7 MUTATION:
8 Does not mutate inputs or external state
9
101. IF n == 0
112. RETURN acc
123. END IF
134. RETURN sumTail(n - 1, acc + n)
14END FUNCTION
15
16FUNCTION sumToTail(n) RETURNS integer
17 INPUT:
18 n : nonnegative integer
19 RETURNS:
20 the sum of all integers from 1 through n
21 MUTATION:
22 Does not mutate inputs or external state
23
241. RETURN sumTail(n, 0)
25END FUNCTIONThe boundary is part of the contract:
1n >= 0A negative n is outside the helper’s contract.
Use the same input:
1sumTail(3, 0)sumTail(3, 0)| Pseudocode line | Result |
|---|---|
Line 1: n == 0 | 3 == 0 is false. |
Line 4: sumTail(n - 1, acc + n) | Call sumTail(3 - 1, 0 + 3), which is sumTail(2, 3). |
sumTail(2, 3)| Pseudocode line | Result |
|---|---|
Line 1: n == 0 | 2 == 0 is false. |
Line 4: sumTail(n - 1, acc + n) | Call sumTail(2 - 1, 3 + 2), which is sumTail(1, 5). |
sumTail(1, 5)| Pseudocode line | Result |
|---|---|
Line 1: n == 0 | 1 == 0 is false. |
Line 4: sumTail(n - 1, acc + n) | Call sumTail(1 - 1, 5 + 1), which is sumTail(0, 6). |
sumTail(0, 6)| Pseudocode line | Result |
|---|---|
Line 1: n == 0 | 0 == 0 is true. |
Line 2: RETURN acc | Return 6. |
Return through the earlier calls:
1sumTail(0, 6) returns 6
2sumTail(1, 5) returns 6
3sumTail(2, 3) returns 6
4sumTail(3, 0) returns 6No call performs arithmetic after its recursive call returns.
1sumTail(0, 0) returns 0
2sumTail(0, 7) returns 7
3sumTail(1, 0) returns 1
4sumTail(3, 0) returns 6The call sumTail(-1, 0) is invalid because negative n is outside the stated contract.
We will show that sumTail(n, acc) returns:
1acc + 1 + 2 + ... + nfor every valid call where n >= 0.
When n == 0, line 2 returns acc.
There are no integers from 1 through 0 to add. The required result is:
1acc + 0 = accThe base case satisfies the helper contract.
Assume n > 0.
Before the recursive call, the required total is:
1acc + (1 + 2 + ... + (n - 1) + n)Line 4 calls:
1sumTail(n - 1, acc + n)The required total for this new call is:
1(acc + n) + (1 + 2 + ... + (n - 1))The total is the same as before the update. The removed value n moved into acc.
The recursive update preserves the stated property.
On every recursive call, n changes from n to n - 1.
Because n starts nonnegative, repeated decreases eventually reach 0. At that point, the base case returns.
For every valid nonnegative n, sumTail(n, acc) terminates and returns the value required by its contract. The wrapper sumToTail(n) calls sumTail(n, 0), so it returns the sum from 1 through n.
Start with n.
Each recursive call decreases it by exactly one:
1n, n - 1, n - 2, ..., 1, 0That produces n + 1 calls, including the base call at 0.
Each call performs constant work:
n with 0;acc, or compute n - 1 and acc + n;Therefore:
1Time = (n + 1) × constant work = O(n)The accumulator itself is one scalar parameter. Its storage does not grow with n.
Source-level tail recursion does not by itself guarantee constant call-stack space.
Without runtime tail-call optimization, calls can remain active until the base case returns:
1sumTail(n, 0)
2sumTail(n - 1, n)
3...
4sumTail(0, ...)Up to n + 1 call frames can be active, so auxiliary stack space is:
1O(n)If a runtime explicitly performs tail-call optimization, the tail-call sequence can use:
1O(1) call-stack spaceThat stack-space result depends on the runtime. Tail-recursive source code alone does not promise it.
Incorrect line:
1RETURN sumTail(n - 1, acc)Exposing input:
1sumTail(3, 0)Wrong states:
1sumTail(3, 0)
2→ sumTail(2, 0)
3→ sumTail(1, 0)
4→ sumTail(0, 0)
5→ 0Wrong result:
10Correction:
1RETURN sumTail(n - 1, acc + n)The current value n must move into the accumulator before n is removed.
Incorrect line:
1IF n == 0
2 RETURN 0Exposing input:
1sumTail(0, 7)Wrong result:
10The helper contract requires:
17 + sum from 1 through 0 = 7Correction:
1IF n == 0
2 RETURN accIncorrect line:
1RETURN n + sumTail(n - 1, acc)Exposing input:
1sumTail(3, 0)Problem:
1n + ...The expression must be evaluated after the recursive call returns. The call is not in tail position. The line also conflicts with the helper contract because acc is not updated to carry the removed value.
The incorrect line can double-count values or produce a helper whose behavior no longer matches its stated contract.
Correction:
1RETURN sumTail(n - 1, acc + n)All accumulation belongs in the argument. Return the recursive call directly.
Incorrect assumption:
1Tail recursion always uses O(1) stack space.Exposing situation:
1A runtime without tail-call optimizationWrong conclusion:
1Stack depth does not grow.In such a runtime, up to n + 1 call frames can still be active.
Correction:
1Tail-recursive source may use O(1) call-stack space only when the runtime performs tail-call optimization.
2Without that guarantee, auxiliary stack space is O(n).Implement these two functions:
1sumTail(n, acc)
2sumToTail(n)sumToTail(n) must call:
1sumTail(n, 0)The executable tests check this contract:
1sumToTail(0) == 0
2sumToTail(3) == 6
3sumTail(0, 7) == 7
4sumToTail(10) == 55Your implementation must preserve the helper contract:
1sumTail(n, acc) returns acc plus the sum from 1 through n1def sum_tail(n, acc):
2 if n == 0:
3 return acc # the accumulator already holds the answer
4 return sum_tail(n - 1, acc + n) # tail call; CPython still keeps every frame
5
6def sum_to_tail(n):
7 return sum_tail(n, 0)
8
9print(sum_to_tail(3), sum_tail(0, 7), sum_to_tail(10))1public class Main {
2 static int sumTail(int n, int acc) {
3 if (n == 0) return acc; // the accumulator already holds the answer
4 return sumTail(n - 1, acc + n); // tail call; the JVM still keeps every frame
5 }
6
7 static int sumToTail(int n) {
8 return sumTail(n, 0);
9 }
10
11 public static void main(String[] args) {
12 System.out.println(sumToTail(3) + " " + sumTail(0, 7) + " " + sumToTail(10));
13 }
14}1#include <iostream>
2using namespace std;
3
4int sumTail(int n, int acc) {
5 if (n == 0) return acc; // the accumulator already holds the answer
6 return sumTail(n - 1, acc + n); // tail call; optimizers may reuse the frame
7}
8
9int sumToTail(int n) {
10 return sumTail(n, 0);
11}
12
13int main() {
14 cout << sumToTail(3) << " " << sumTail(0, 7) << " " << sumToTail(10) << endl;
15}1function sumTail(n, acc) {
2 if (n === 0) return acc; // the accumulator already holds the answer
3 return sumTail(n - 1, acc + n); // tail call; V8 still keeps every frame
4}
5
6function sumToTail(n) {
7 return sumTail(n, 0);
8}
9
10console.log([sumToTail(3), sumTail(0, 7), sumToTail(10)].join(' '));In non-tail recursion work remains after the call, as in n + sumTo(n - 1). In tail recursion the call is the last action and the work moved into an argument, as in sumTail(n - 1, acc + n).
A runtime feature that reuses the current stack frame for a call in tail position instead of adding a new one. It makes the call chain run in O(1) stack space. The source being tail recursive does not guarantee it.
Python and Java do not. V8, the engine behind Node and Chrome, does not either. C and C++ compilers often do at higher optimization levels, but the language does not promise it.
Pass the product so far: factorialTail(n, acc) returns acc when n is 0, otherwise factorialTail(n - 1, acc * n), started with acc = 1. The multiplication happens before the call, so nothing waits.
Turn the tail call into a loop. The state (n, acc) becomes two variables: while n > 0, set acc += n and n -= 1. The result is the same with O(1) space and no stack growth.