Chapter 28 • Data Structure • Complete Notes
Tail Recursion and Removal of Recursion: C Programs & Examples
Understand tail calls, recursion removal, loop conversion, manual stack techniques, C programs, dry runs, complexity, memory tricks and solved university-style questions.
Many students can write a recursive factorial program, but they become confused when a teacher asks, "Is this tail recursion?" or "Remove recursion and write the same program using a loop." Both questions are common in Data Structure exams. They become easy once we understand what happens after a recursive call returns.
In this chapter, we will learn the idea slowly, convert programs one step at a time and explain why removing recursion can save stack memory. You will also see an important point: not every recursive program can be changed into a simple loop without storing extra information.
Quick Answer
Tail recursion is a form of recursion in which the recursive call is the last operation performed by the function on that path. After the call returns, no multiplication, addition or other calculation remains in the caller.
Removal of recursion means rewriting a recursive algorithm so it works without recursive function calls. We may use a loop, an accumulator or an explicit stack depending on the problem.
1. What Is Tail Recursion in Data Structure?

In recursion, a function calls itself to solve a smaller version of the same problem. Every correct recursive algorithm must eventually reach a stopping condition, called the base case.
Tail recursion has an extra rule: the recursive call must finish the current branch. The caller has no pending work after that call.
For the basics of function calls and base cases, first see Recursion in Data Structure: Types, Working, Examples and Applications.
Work is pending
return n * fact(n-1);
The function still needs to multiply by
n after
fact(n-1) returns.
Nothing is pending
return fact(n-1, n*acc);
The multiplication is completed before making the next call. The recursive call directly supplies the answer.
The Difference in One Diagram
Normal Factorial
Tail Factorial
2. How Does Tail Recursion Work? Easy Example
Suppose we want to print 4, 3, 2, 1. We first print the current number and then call the same function using a smaller number.
#include <stdio.h>
void countdown(int n) {
if (n <= 0) return;
printf("%d ", n);
countdown(n - 1);
}
int main(void) {
countdown(4);
return 0;
}
// Output: 4 3 2 1
Here the printf statement executes
first. The call countdown(n-1)
comes last. Nothing needs to be calculated
after the deeper call finishes, so this is
tail recursion.
Countdown Call Flow
Notice: This describes the logical operation. Whether the compiler actually reuses one stack frame is a separate question.
3. Tail Recursion vs Head and Non-Tail Recursion
Students often confuse the position of the recursive call with the output order. Compare these three examples carefully.
| Type | Main Idea | Example | Typical Result |
|---|---|---|---|
| Tail recursion | Recursive call is last; no pending work | Print then call f(n-1) |
Prints 3 2 1 |
| Head recursion | Recursive call appears before main work | Call f(n-1) then print |
Prints 1 2 3 |
| Non-tail recursion | More work remains after recursive call | return n * fact(n-1); |
Multiplication happens while returning |
/* Tail recursion: print before the call */
void down(int n) {
if (n == 0) return;
printf("%d ", n);
down(n - 1);
}
/* Head recursion: print after the call */
void up(int n) {
if (n == 0) return;
up(n - 1);
printf("%d ", n);
}
/* down(3) prints 3 2 1 */
/* up(3) prints 1 2 3 */
Calling a function recursively does not automatically make it tail-recursive. Look at what the caller must do after the call returns.
4. Normal Factorial vs Tail-Recursive Factorial in C
Factorial is the best example for understanding the conversion. For a non-negative integer n, factorial means multiplying all positive integers from 1 to n.
For example, 4! = 4 × 3 × 2 × 1 = 24. By definition, 0! = 1.
4.1 Normal Recursive Factorial
unsigned long long factNormal(int n) {
if (n <= 1) return 1ULL;
return (unsigned long long)n * factNormal(n - 1);
}
For factNormal(4), the calls
go down to 1. During the return phase,
the waiting multiplications complete:
2 × 1 = 2, then 3 × 2 = 6,
then 4 × 6 = 24.
Since multiplication takes place after the recursive call, this is not tail recursion.
4.2 Tail-Recursive Factorial Using an Accumulator
An accumulator is an extra variable that carries the result calculated so far. It removes the need to multiply anything after the recursive call returns.
unsigned long long factTail(
int n,
unsigned long long acc
) {
if (n <= 1) return acc;
return factTail(
n - 1,
acc * (unsigned long long)n
);
}
/* Call factTail(4, 1ULL) to get 24. */
| Call | n | Accumulator (acc) | Next Step |
|---|---|---|---|
| 1 | 4 | 1 | Call tail(3, 4) |
| 2 | 3 | 4 | Call tail(2, 12) |
| 3 | 2 | 12 | Call tail(1, 24) |
| 4 | 1 | 24 | Return 24 |
Every call already carries the partial answer.
When n reaches 1, the function simply returns
acc. There is no unfinished
multiplication.
5. What Is Removal of Recursion?
Removal of recursion or
recursion elimination means
changing an algorithm so it does not call itself.
A new version may use a for loop,
while loop, an accumulator or
an explicitly managed stack.
The reason is simple: very deep recursion can use a lot of call-stack memory. For straightforward tasks, a loop can often perform the same work with fewer active function calls.
The idea of converting functions into loops is easier when you first understand the difference between an algorithm and its implementation. You can revise that foundation in Algorithm in Data Structure: Characteristics, Steps and Examples.
Recursion Elimination
6. How to Convert Tail Recursion into Iteration
When a recursive call is in tail position, the conversion is often direct. We use a loop to update the function's changing parameters.
- Identify the base case. It becomes the loop's stopping rule.
- Identify the values passed to the next recursive call.
- Store these values in variables and update them inside the loop.
- Return the same result when the stopping condition is reached.
- Test the original and converted methods with the same small inputs.
6.1 Convert Tail Factorial to a While Loop
unsigned long long factLoop(int n) {
unsigned long long acc = 1ULL;
while (n > 1) {
acc = acc * (unsigned long long)n;
n = n - 1;
}
return acc;
}
Compare it with the tail-recursive version.
In recursion, n and
acc are passed as arguments;
in iteration, those same values are updated
inside the while loop.
| Round | n Before | acc Before | acc After | n After |
|---|---|---|---|---|
| 1 | 4 | 1 | 4 | 3 |
| 2 | 3 | 4 | 12 | 2 |
| 3 | 2 | 12 | 24 | 1 |
| Stop | 1 | 24 | Return 24 | — |
7. Complete C Program: Normal, Tail and Iterative Factorial
This single program shows all three methods together. For this demonstration, inputs are restricted to 0 through 20, since 20! fits in a 64-bit unsigned integer but 21! does not.
#include <stdio.h>
unsigned long long normalFact(int n) {
if (n <= 1) return 1ULL;
return (unsigned long long)n *
normalFact(n - 1);
}
unsigned long long tailFact(
int n,
unsigned long long acc
) {
if (n <= 1) return acc;
return tailFact(
n - 1,
acc * (unsigned long long)n
);
}
unsigned long long loopFact(int n) {
unsigned long long acc = 1ULL;
while (n > 1) {
acc *= (unsigned long long)n;
n--;
}
return acc;
}
int main(void) {
int n = 5;
if (n < 0 || n > 20) {
puts("Choose a number from 0 to 20.");
return 1;
}
printf("Normal: %llu\n", normalFact(n));
printf("Tail: %llu\n", tailFact(n, 1ULL));
printf("Loop: %llu\n", loopFact(n));
return 0;
}
/* Output:
Normal: 120
Tail: 120
Loop: 120
*/
The answer is the same in all three methods. What changes is when multiplication happens and how active work is stored.
8. Example Two: Tail-Recursive GCD and Loop Conversion
GCD means Greatest Common Divisor. For example, the GCD of 48 and 18 is 6 because 6 is the largest positive number that divides both values exactly.
Euclid's algorithm repeatedly replaces
the pair (a,b) with
(b,a%b) until b
becomes zero. The recursive call is the
final operation, so the recursive form
is tail-recursive.
int gcdTail(int a, int b) {
if (b == 0) return a;
return gcdTail(b, a % b);
}
int gcdLoop(int a, int b) {
while (b != 0) {
int remainder = a % b;
a = b;
b = remainder;
}
return a;
}
/* For positive a = 48 and b = 18:
Both functions return 6. */
| Step | a | b | a % b |
|---|---|---|---|
| 1 | 48 | 18 | 12 |
| 2 | 18 | 12 | 6 |
| 3 | 12 | 6 | 0 |
| 4 | 6 | 0 | Stop |
For positive integers, both versions take O(log(min(a,b))) time in the worst case. The loop uses O(1) auxiliary space, while a recursive implementation without tail-call optimisation uses O(log(min(a,b))) call-stack space in the worst case.
9. Can We Remove Non-Tail Recursion?
Yes, but the conversion may be more complicated. With non-tail recursion, the function must remember some work after each deeper call finishes.
A simple loop may work for special cases such as factorial, but more general problems need an explicit stack to remember unfinished work.
9.1 Remove Non-Tail Factorial Using a Loop
Even though n * factorial(n-1)
is not tail-recursive, factorial can still
be calculated with a normal loop because
multiplication can be accumulated directly.
unsigned long long factorial(int n) {
unsigned long long result = 1ULL;
for (int i = 2; i <= n; i++) {
result *= (unsigned long long)i;
}
return result;
}
However, this easy conversion does not mean every non-tail recursive algorithm can be changed into the same kind of loop.
9.2 Remove Head Recursion Using an Explicit Stack
Consider printUp(4), which first
calls printUp(3) and prints 4
only while returning.
To reproduce this order without recursive calls, we can store the values in a stack and then remove them in reverse order.
#include <stdio.h>
#define LIMIT 100
void printUpNoRecursion(int n) {
int stack[LIMIT];
int top = -1;
if (n < 0 || n > LIMIT) {
puts("Input outside 0..100.");
return;
}
while (n > 0) {
stack[++top] = n;
n--;
}
while (top >= 0) {
printf("%d ", stack[top--]);
}
}
int main(void) {
printUpNoRecursion(4);
return 0;
}
// Output: 1 2 3 4
Why a Stack Helps
Push values
Pop and print
The manual stack takes O(n) extra memory here. Removing recursive calls does not automatically remove all stack-like memory requirements.
An equivalent simpler loop that counts upward also exists for this specific example, but a manual stack makes the general idea easy to see.
10. General Method: Remove Recursion Using a Stack
Some recursive algorithms explore many branches, for example tree traversal and graph depth-first search.
The program must remember which branch to visit next. In such cases, an explicit stack can replace the program's call stack.
- Create a stack to hold unfinished tasks, nodes or function states.
- Push the starting task onto the stack.
- Repeat while the stack is not empty.
- Pop one task and perform the required work.
- Push its unfinished subtasks in the correct order.
- Stop when the stack becomes empty.
push(start)
while stack is not empty:
current = pop()
process(current)
push unfinished tasks in required order
Why the order matters: A stack is LIFO. If you want a left subtree to be processed before the right subtree, an iterative preorder traversal usually pushes the right child first, followed by the left child.
In a graph, a visited set may also be necessary to avoid repeating nodes. The exact stack state depends on the recursive algorithm.
11. Tail-Call Optimisation vs Manual Removal of Recursion
These two ideas sound similar, but they are not exactly the same.
| Point | Tail-Call Optimisation | Manual Recursion Removal |
|---|---|---|
| Performed by | Compiler or runtime, when supported | Programmer rewriting the algorithm |
| Source code | May still look recursive | Uses loops or explicit stacks |
| Guaranteed in C? | No | The loop structure is explicit |
| Stack memory | Can avoid growth for suitable calls | Depends on loop or manual stack |
| Main benefit | Optimises eligible tail calls | Gives predictable control over execution structure |
Therefore, never write that "tail recursion always uses O(1) space in C." State the compiler optimisation assumption when it matters.
12. Time and Space Complexity Comparison
When analysing a recursive program, count the number of calls and the maximum number of active calls.
When analysing the converted program, count loop iterations and any extra stack or array you have introduced.
| Problem / Method | Time | Auxiliary Space |
|---|---|---|
| Normal factorial | O(n) | O(n) call stack |
| Tail factorial, no tail-call optimisation | O(n) | O(n) call stack |
| Tail factorial, optimised tail calls | O(n) | O(1) call-stack use |
| Iterative factorial | O(n) | O(1) |
| Recursive countdown | O(n) | O(n) without optimisation |
| Countdown loop | O(n) | O(1) |
| Head-recursive print n numbers | O(n) | O(n) |
| Explicit-stack print example | O(n) | O(n) |
| GCD with a loop (positive inputs) | O(log(min(a,b))) worst case | O(1) |
These space counts assume fixed-width integer variables. For very large integers, the storage required for the numbers themselves also matters.
13. Advantages of Tail Recursion and Recursion Removal
Easier Loop Conversion
Tail calls often translate into straightforward
updates inside a while loop.
Clear State Changes
Accumulator variables show the partial answer at each step.
Less Stack Usage
Many converted loops avoid growing the call stack as the input increases.
Useful for Large Inputs
Removing unnecessary recursive calls can reduce stack-overflow risk.
Limitations and Trade-Offs
- Making a function tail-recursive may require extra parameters such as an accumulator.
- A loop may be less natural for some recursive structures such as trees.
- Replacing a recursive algorithm with a manual stack can make the program longer.
- Tail-call optimisation is not guaranteed in C.
- Changing the order of operations can change the output if the conversion is incorrect.
14. Common Mistakes Students Should Avoid
Mistake 1: Last Line Means Tail Recursion
return n * f(n-1); may be the last
line, but multiplication is still pending.
It is not tail recursion.
Mistake 2: Forgetting the Base Case
The new function or loop must stop at the correct point. Otherwise it may not terminate.
Mistake 3: Changing Parameter Values Incorrectly
Update loop variables in the same logical order as recursive arguments. Temporary variables can help.
Mistake 4: Assuming O(1) Space Automatically
Unoptimised tail recursion still builds calls; a manual stack may also take O(n) space.
Mistake 5: Losing Return Order
For head recursion and tree traversal, returned work often needs reverse-order handling.
Mistake 6: Ignoring Large Inputs
Factorial values can overflow fixed-width integers, even when the recursion itself is correct.
15. Memory Tricks for Exams and Viva
Tail Recursion
Last Action = Self-call; Tasks finished.
Accumulator
Accumulate → Carry → Complete.
Recursion Removal
Base case → Update state → Loop.
For a 5-mark exam answer, remember this order: Definition → Diagram → Example → Dry Run → Complexity. This makes the explanation easy to follow.
16. PYQ-Style Important Questions with Solved Answers
Accuracy note: The following are original, previous-year-paper-style practice questions based on common university exam patterns. They are not claimed to be verified questions from a named past exam paper.
2 Marks — Q1
Define Tail Recursion.
Answer: Tail recursion is a type of recursion in which the recursive call is the final operation in a function branch. No calculation remains after the recursive call returns.
2 Marks — Q2
What Is Removal of Recursion?
Answer: Removal of recursion is the process of rewriting a recursive algorithm without recursive function calls, usually using iteration or an explicit stack.
2 Marks — Q3
Why Is return n * f(n-1) Not Tail Recursion?
Answer: Because multiplication by n is still pending after the recursive call returns. The recursive call is not the last operation.
5 Marks — Q4
Explain Tail Recursion with an Example.
Answer:
In tail recursion, a function makes a recursive
call as its final operation. For factorial,
an accumulator stores the result calculated
so far:
tail(n, acc) calls
tail(n-1, n*acc).
Starting at tail(4,1), the calls
are tail(3,4),
tail(2,12),
tail(1,24).
The last call returns 24 directly.
No multiplication remains after any
recursive call.
5 Marks — Q5
Convert Tail-Recursive Factorial into Iteration.
Answer:
Start with acc=1.
Repeat while n>1:
multiply acc by n,
then decrease n by one.
Return acc after the loop.
The complete C function is shown in Section 6. Both versions give 24 for input 4; the loop avoids recursive calls.
5 Marks — Q6
Differentiate Tail Recursion and Non-Tail Recursion.
Answer: In tail recursion, the recursive call is the final operation and no work remains afterwards. In non-tail recursion, the caller has unfinished work after the call returns.
For example,
return f(n-1, acc*n);
is tail-recursive, while
return n*f(n-1); is not.
Tail recursion is often easier to convert
to a loop.
10 Marks — Q7
Explain Removal of Recursion with Techniques, Examples and Complexity.
Answer: Recursion removal means rewriting an algorithm without recursive function calls. A tail-recursive function can often be converted directly into a loop by maintaining its parameters as changing variables.
Normal factorial can also be replaced by an iterative multiplication loop. For branching and order-sensitive recursion, an explicit stack may be required to remember pending tasks.
Recursive factorial takes O(n) time and generally O(n) stack space without optimisation, while iterative factorial takes O(n) time and O(1) auxiliary space.
The converted algorithm must preserve the base case, output and operation order.
17. Practice MCQs with Answers
Q1. Which statement is tail-recursive? A) return n*f(n-1) B) return f(n-1) C) return 1+f(n-1) D) return f(n-1)*2
Correct answer: B. The recursive call is returned directly, so nothing remains to be done afterwards.
Q2. What is the main purpose of an accumulator? A) Store partial result B) Sort data C) Allocate an array D) Read input
Correct answer: A. An accumulator carries the result calculated so far from one call to the next.
Q3. In C, is O(1) stack memory guaranteed for tail recursion? A) Yes B) No
Correct answer: B. The C language does not guarantee tail-call optimisation.
Q4. Which structure can replace recursive calls in general DFS? A) Stack B) Only one counter C) String D) None
Correct answer: A. An explicit stack can store pending nodes or tasks.
Q5. What is the output of tailFactorial(4,1)? A) 4 B) 10 C) 24 D) 120
Correct answer: C (24). The accumulator becomes 1 → 4 → 12 → 24.
Q6. Which operation is still pending in normal recursive factorial? A) Division B) Multiplication C) Sorting D) Input
Correct answer: B.
After fact(n-1) returns,
the caller multiplies by n.
18. Frequently Asked Questions
Is every recursive function tail-recursive?
No. A recursive function is tail-recursive only when the recursive call is the final operation of that path. Normal factorial is an example of non-tail recursion.
Is tail recursion faster than normal recursion?
Not always. It may allow compiler optimisation, but the actual performance depends on the compiler and algorithm. Both factorial versions perform O(n) arithmetic operations.
Can every recursion be removed?
Many recursive algorithms can be rewritten iteratively, but some need an explicit stack or other state to preserve the original behaviour. The transformed algorithm may be longer.
What is the difference between recursion removal and tail-call optimisation?
Recursion removal changes the source algorithm to use a loop or manual stack. Tail-call optimisation is performed by a compiler or runtime for eligible calls when supported.
Why is stack memory important in recursion?
Active recursive calls normally occupy stack frames. If recursion becomes very deep, the available stack space may be exhausted.
Which example should I learn first for exams?
Start with countdown, normal factorial, tail-recursive factorial and iterative factorial. Then learn GCD and an explicit-stack example.
19. One-Minute Revision
Tail Recursion
Recursive call is the last operation.
Non-Tail
Work remains after the recursive call.
Accumulator
Carries partial results forward.
Recursion Removal
Replace self-calls with a loop or manual stack.
Factorial Loop
O(n) time, O(1) auxiliary space.
Compiler Rule
Tail-call optimisation is not guaranteed in C.
Conclusion
Tail recursion is easier to understand when you ask one question: "Does the function have anything left to do after calling itself?" If the answer is no, the call is in tail position.
Removal of recursion means solving the same problem without recursive calls. For a simple tail-recursive function, we often use a loop and update variables. For a problem with unfinished branches or return-order work, we may need a manual stack.
For university exams, practise converting factorial step by step, trace the accumulator values and remember the difference between tail recursion and guaranteed compiler optimisation. Once these ideas are clear, recursion elimination questions become much easier.
