Tail Recursion Problem

In this article, we will discuss tail recursion. The tail recursion is that kind of recursion in which the recursive call is made at the end of the function. In other words, no statement exists after the recursive call.

Let us consider the following in C++ that demonstrates how tail recursion works:

Source Code:

// Header file
#include <bits/stdc++.h>
using namespace std;

// Function
void myFunction(int number)
{
// If n becomes greater than 10
// then return
if (number > 10)
return;

// Print the number
cout << " " << number;

// The last executed statement is recursive call
myFunction(number + 1);
}

// Main() function
int main() {

// Initialize an integer
int number = 1;

// Call myFunction
myFunction(number);
return 0;
}

Output:

write your code here: Coding Playground

Please note that in the above program there is no statement to be executed after the recursive call.

Need for the tail recursion

The tail recursion is always preferred over the non-tail recursion as the compiler can easily optimized tail recursion.

The compiler is generally responsible for executing recursive statements with the help of a stack. The stack keeps all the necessary information including the value of parameters for each and every recursive call. Whenever there is a call made to a procedure, the information is passed to the stack, and the moment when the execution of the function ends, the information is popped out or removed from the stack. So, the problem that persists with the non-tail recursion functions is that non-tail recursive functions take more stack depth as compared to tail recursion.

How the compiler optimizes tail recursion?

The tactic utilized by the compiler to optimize the tail recursion is simple. Actually, there is no statement to be executed after the tail recursive statement so the compiler doesn’t have to worry about saving the current function’s stack frame.

How to convert a non-tail recursion into tail recursion?

We can convert most of the non-tail recursive functions into tail recursion. For example, consider the following program that computes the sum of the first N natural numbers. The below program looks like a tail recursion but it is not actually. This is because first, we calculate the result of the operation myFunction(number + 1) and then apply the addition with the number and then return the entire value. So calling the recursive function is not the last thing being done here.

Source Code

// Header file
#include <bits/stdc++.h>
using namespace std;

// Function
int myFunction(int number)
{
// If n becomes equal to 10
// then return it
if (number == 10)
return number;

// Sum number with the result of myFunction(number + 1)
// and then return the entire value
return number + myFunction(number + 1);
}

// Main() function
int main() {

// Initialize an integer
int number = 1;

// Call myFunction
cout << myFunction(number);
return 0;
}

Output:

write your code here: Coding Playground

We can easily convert the above non-tail recursion into tail recursion. The idea is to pass an additional argument to myFunction and return the recursive call as a whole at the end of the function. For example, consider the following that computes the sum of N natural numbers using tail recursion:

Source Code:

// Header file
#include <bits/stdc++.h>
using namespace std;

// Function
int myFunction(int sum, int number)
{
// If n becomes greater than 10
// then return it
if (number > 10)
return sum;

// Just return the result of the
// recursive call
return myFunction(sum + number,number + 1);
}

// Main() function
int main() {

// Initialize an integer
int number = 1;

// Call myFunction
cout << myFunction(0, number);
return 0;
}

write your code here: Coding Playground

Output:

Conclusion

In this article, we discussed an important data structures concept, tail recursion. We believe that you must have learned something new through this article.

Menu

Need for the tail recursion

How the compiler optimizes tail recursion?

How to convert a non-tail recursion into tail recursion?

Conclusion

Mark Lesson Complete (Tail Recursion Problem)

Menu

Tail Recursion Problem

Course Lessons

Free DSA Resources: Courses, YouTube Channels & 2026 Roadmap

A Career in Digital Marketing - A Complete Guide for Beginners

Structure of DBMS Explained: Components, Diagram & Architecture

Advanced Algorithms and Problem Solving Techniques

Data Structures: Foundation of Effective Programming

Importance of Banks: Role of Banking System in Economy, Business & Development

What Is Marketing? Definition, Types and Importance

STP Marketing Framework: Segmentation, Targeting and Positioning

What Is Branding? Meaning, Elements and Importance

What Is Digital Marketing and Why It Matters in India

Product Life Cycle: The 4 Stages Explained

Indian Brand Success Stories & Lessons

Content Marketing Strategy: A Step-by-Step Framework

Evolution of Marketing: Eras and Orientations

SEO vs SEM: Differences, Pros and Cons

GE-McKinsey Matrix: The Nine-Box Portfolio Model

Marketing Frameworks Cheat Sheet: Quick Reference

Email Marketing Best Practices That Drive Results

Influencer Marketing Strategy: A Complete Guide

The 9 Digital Marketing Channels Explained

Core Branding Concepts: Identity, Image and Equity

Marketing Mix Explained: The 4Ps and 7Ps

Sales vs Marketing: Key Differences Explained

Goods vs Services Marketing: What's the Difference?

AIDA Model: The 4 Stages of the Customer Journey

Brand Architecture Models: Branded House vs House of Brands

The Digital Marketing Funnel: Awareness to Conversion

B2B vs B2C Marketing: Differences, Examples and Strategy

BCG Matrix Explained: Stars, Cash Cows, Dogs & Question Marks

Case Study Frameworks for Analytics Interviews

Brand Extension vs Line Extension: Strategy, Fit and Risks

Digital Marketing Terms: CPC, CTR, ROAS and More

Kapferer's Brand Identity Prism: The 6 Facets

Ansoff Matrix: The 4 Growth Strategies with Examples

Customer Psychology in Marketing: Needs and Buyer Behaviour

Marketing Terms & Jargon: A Beginner Glossary

Porter's Five Forces: Industry Analysis Framework

Digital Marketing Jobs and Career Roles in India

Brand Positioning Bullseye Framework

PESTLE Analysis: Meaning, Factors and India FMCG Examples

Essential Digital Marketing Tools & Platforms for India

Co-Branding and Brand Personality Explained

What Is Brand Architecture? Types and Examples

AI and GenAI in Analytics - The Modern Analyst's Toolkit

Analytics Metrics Deep-Dive: A/B Testing and Retention

Brand Extension vs Line Extension: Meaning & Examples

Brand Differentiation: Practical Levers to Make a Brand Stand Out

Digital Marketing Frameworks for Campaign Planning

SWOT Analysis: How to Build One with Examples

Brand Equity Measurement and Brand Valuation

Social Media Marketing in India: Platform Selection Guide

Keller's Brand Equity Model (CBBE Pyramid) Explained

The Marketing Environment: Micro and Macro Factors

Introduction to Big Data

Introduction to Deep Learning: From Basics to Advanced Concepts

Step-by-Step Guide to Data Visualization with Power BI

How To Start Your Career In Data Science

Data Communication: Process, Components, Types & Models for Networks

Basics of Javascript

Why is it Important for Freshers to Work in a Team?

The Multifaceted Relationships Between Banker and Customer

What are Node.js and Basics of Node.js?

Does a Linkedin profile really matter before getting a Job?

10 Common Data Structures Every Programmer Must Know

6 Bootstrap Tools and Playground – One-stop shop for all Web Developmental Needs

Introduction to Management Interview Preparation

Why Learn English?

Grooming and Etiquette: Complete Guide for Professional and Corporate Success

Getting Started with Tableau: Installation and Introduction

Discover the Versatility of Microsoft Excel: Your Swiss Army Knife for Data

What is Marketing? Core Concepts and Evolution of Marketing Eras

Header in C++

Ultimate Guide to HR Interview Questions for Freshers

JSON vs XML: Differences

Why Social Media Marketing Is Important?

Why Data Visualization is Important for Becoming a Data Scientist

Most Common 10 Telephonic Interview Questions