---
title: "Tail and non-tail recursion"
subject: "Data Structure and Algorithm"
chapter: 5
key: "semester_4/data_structure_and_algorithm:tail-vs-nontail-recursion"
source: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/tail-vs-nontail-recursion
site: BCT Engineering
---

# Tail and non-tail recursion

Data Structure and Algorithm · Chapter 5: Recursion

- Asked in: 2070 Magh, 3 marks
- Video: [Types of Recursion (Part 2) | Tail & Non-tail Recursion](https://www.youtube.com/watch?v=HIt_GPuD7wk) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_4/data_structure_and_algorithm/tail-vs-nontail-recursion
- Whole chapter: https://www.bctengineer.com/md/semester_4/data_structure_and_algorithm/chapter-5

## Question

What is tail and non-tail recursion with example?

## Short answer

Tail recursion: the recursive call is the last operation, so the stack frame can be reused and the recursion optimized into a loop (e.g., factorial with accumulator). Non-tail recursion: work remains after the call (e.g., n * fact(n-1)), so the full call stack is needed.

## Answer

**Tail recursion:** a recursive call is a tail call if it is the very last thing the function does. Nothing is left to do after the call returns, so the result of the inner call is the result of the function. A compiler can reuse the same stack frame, which turns the recursion into a loop.

```c
/* tail recursive: factorial with accumulator */
int fact(int n, int acc) {
    if (n == 0) return acc;
    return fact(n - 1, n * acc);   /* last action is the call */
}
```
`fact(4,1)` → `fact(3,4)` → `fact(2,12)` → `fact(1,24)` → `fact(0,24)` = 24. No pending multiplication stays on the stack.

**Non-tail recursion:** some work is still pending after the recursive call returns, so every frame must stay on the stack until the calls unwind.

```c
/* non-tail recursive factorial */
int fact(int n) {
    if (n == 0) return 1;
    return n * fact(n - 1);   /* multiplication after the call */
}
```
`fact(4)` = 4 × fact(3) = 4 × (3 × (2 × (1 × 1))). Four frames wait for the result. Tower of Hanoi, tree traversals and Fibonacci `fib(n-1)+fib(n-2)` are also non-tail.

| Point | Tail recursion | Non-tail recursion |
|---|---|---|
| Work after the call | none | yes (multiply, add, print) |
| Stack space | O(1) with optimisation | O(n) |
| Conversion to loop | easy | needs an explicit stack |

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What makes a recursive call a tail call?
   A. It appears first in the function
   B. It is inside a loop
   C. It is the last action; nothing remains to do after it returns
   D. It returns void
   Answer: C. The inner result is the function's result, so the frame can be reused. (Key point: Tail recursion)

2. Which function is tail recursive?
   A. return n * fact(n-1)
   B. fib(n-1) + fib(n-2)
   C. TOH with two calls
   D. fact(n, acc) returning fact(n-1, n*acc)
   Answer: D. In the others work remains after the call. (Key point: Which is tail)

3. Stack space for tail vs non-tail recursion?
   A. O(1) with optimisation vs O(n)
   B. O(n) vs O(1)
   C. Both O(1)
   D. Both O(n) always
   Answer: A. Tail calls reuse one frame; non-tail frames wait. (Key point: Stack space)

## Related in Data Structure and Algorithm

- [Is recursion slow; recursive vs non-recursive](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-slow-compare) — Data Structure and Algorithm, chapter 5