Tail Recursion and Removal of Recursion: C Programs & Examples

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.

Easy Indian English Step-by-Step Diagrams C Programs 2 / 5 / 10 Marks

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?

Tail Recursion and Removal of Recursion: C Programs & Examples

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.

Not Tail Recursive

Work is pending

return n * fact(n-1);

The function still needs to multiply by n after fact(n-1) returns.

Tail Recursive

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

fact(4) 4 × fact(3) 3 × fact(2) 2 × fact(1) Multiply while returning

Tail Factorial

tail(4, 1) tail(3, 4) tail(2, 12) tail(1, 24) Return 24 directly
Normal recursion waits to multiply during returns; tail recursion carries the completed work into the next call.
Memory Trick — LAST: Last Action is a Self-call; There is no work left afterwards. This is a quick way to recognise tail recursion.

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.

C Example: Tail-Recursive Countdown
#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

countdown(4) → countdown(3) → countdown(2) → countdown(1) → countdown(0): STOP
Each call prints one number and hands the remaining work to the next call.

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
Compare the Call Position
/* 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

Normal Recursion — Multiplication Is Pending
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.

Tail Recursion — Accumulator Method
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
141Call tail(3, 4)
234Call tail(2, 12)
3212Call tail(1, 24)
4124Return 24

Every call already carries the partial answer. When n reaches 1, the function simply returns acc. There is no unfinished multiplication.

Memory Trick — ACC: Accumulate the answer, Carry it to the next call, Complete the result at the base case.

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

Recursive Function → Identify Repeated State → Write Loop or Manual Stack → Same Correct Result
The goal is to preserve the algorithm's behaviour while removing recursive function calls.

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.

  1. Identify the base case. It becomes the loop's stopping rule.
  2. Identify the values passed to the next recursive call.
  3. Store these values in variables and update them inside the loop.
  4. Return the same result when the stopping condition is reached.
  5. Test the original and converted methods with the same small inputs.

6.1 Convert Tail Factorial to a While Loop

C Program — Tail Recursion Removed
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
14143
234122
3212241
Stop 1 24 Return 24 —
Important compiler fact: Tail recursion can allow tail-call optimisation, where a compiler reuses a stack frame. However, C does not guarantee this optimisation. Without it, the tail-recursive factorial still uses O(n) call-stack space. The explicitly iterative version uses O(1) auxiliary space for fixed-width integers.

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.

factorial_comparison.c — Complete Runnable Program
#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.

C Functions — Euclidean GCD
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
1481812
218126
31260
460Stop

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.

Non-Tail Factorial Converted to a Loop
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.

C Program — Manual Stack Replaces Recursive Returns
#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

Top: 1 2 3 Bottom: 4

Pop and print

Pop 1 Pop 2 Pop 3 Pop 4
Last In, First Out (LIFO) gives the same output order as returns from the recursive calls.

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.

  1. Create a stack to hold unfinished tasks, nodes or function states.
  2. Push the starting task onto the stack.
  3. Repeat while the stack is not empty.
  4. Pop one task and perform the required work.
  5. Push its unfinished subtasks in the correct order.
  6. Stop when the stack becomes empty.
General Pseudocode — Iterative Depth-First Work
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.

Important distinction: A tail-recursive function often converts directly to a loop. A branching recursive function may require an explicit stack or another data structure. Both are called recursion removal, but their extra memory requirements can be different.

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

Benefit 01

Easier Loop Conversion

Tail calls often translate into straightforward updates inside a while loop.

Benefit 02

Clear State Changes

Accumulator variables show the partial answer at each step.

Benefit 03

Less Stack Usage

Many converted loops avoid growing the call stack as the input increases.

Benefit 04

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

LAST

Tail Recursion

Last Action = Self-call; Tasks finished.

ACC

Accumulator

Accumulate → Carry → Complete.

BUL

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.

Tags

Post a Comment

0 Comments
* Please Don't Spam Here. All the Comments are Reviewed by Admin.
Join Telegram Exam updates and free resources