Tail vs Non Tail Recursion – Recursion Playlist C++ – Recursion Types in Data Structure

🔁 What is Recursion?

Recursion is when a function calls itself to solve a smaller subproblem.

🧠 Tail Recursion vs Non-Tail Recursion

Feature	Tail Recursion	Non-Tail Recursion
Definition	The last action is the recursive call	The recursive call is not the last action
Optimization	Can be optimized by the compiler (tail call optimization)	Cannot be optimized
Call stack usage	Uses less stack (can be optimized away)	Uses more stack (each call waits)
Return after call?	❌ No further work after recursion	✅ More work is done after the recursive call

✅ Tail Recursion Example in C++

#include <iostream>
using namespace std;

void tailRecursion(int n) 
{
    if (n == 0) 
       return;
    cout << n << " ";
    tailRecursion(n - 1); // recursive call is the LAST statement
}

int main() 
{
    tailRecursion(5);  // Output: 5 4 3 2 1
    return 0;
}

✅ Tail Recursive because there’s nothing left to do after the recursive call.

Only one box (stack frame) is used the whole time.

❌ Non-Tail Recursion Example in C++

#include <iostream>
using namespace std;

int nonTailFactorial(int n) 
{
    if (n == 0) 
       return 1;
    return n * nonTailFactorial(n - 1);  // work (multiplication) after recursion
}

int main() 
{
    cout << nonTailFactorial(5);  // Output: 120
    return 0;
}

❌ Non-Tail Recursive because multiplication (n * ...) happens after the recursive call returns.

A new stack frame for each function call – and each call waits for the next one to finish. That uses more memory.

🧠 Why Tail Recursion is Better (Sometimes)

Tail-recursive functions can be optimized by the compiler using Tail Call Optimization (TCO) — this means:

• The compiler reuses the current function’s stack frame
• Saves memory and prevents stack overflow

But: C++ compilers don’t always apply this optimization unless explicitly told and supported by flags.