Select Page

# What is a Proper Tail Call?

Kashish Kumar
Published: June 17, 2022

What is a Proper Tail Call?

Proper tail calls (PTC) is a programming language feature that enables memory-efficient recursive algorithms. Tail call optimization is where you can avoid allocating a new stack frame for a function because the calling function will simply return the value it gets from the called function. The most common use is tail-recursion, where a recursive function written to take advantage of tail-call optimization can use constant stack space.

Proper Tail Call optimization means you can call a function from another function without increasing the call stack.

• Programs that use Proper Tail Call may experience a low memory footprint because the garbage collector is more likely to collect certain local objects.
• It  Reduces the stack usage, thus reducing the amount of cache space needed, freeing up cache space for other memory accesses.

Example 1: Finding the Greatest common divisor of two numbers using tail recursion

## C++

 `#include ``using` `namespace` `std;`` ` `int` `gcd(``int` `a, ``int` `b)``{``    ``if` `(b == 0) {``        ``return` `a;``    ``}`` ` `    ``    ``return` `gcd(b, a % b);``}`` ` `int` `main()``{``    ``int` `a = 4, b = 8;`` ` `    ``    ``cout << gcd(a, b);``    ``return` `0;``}`

Time Complexity: O(log(max(a, b)))
Auxiliary Space: O(1)

Example 2:  Program to calculate the multiplication of a number with two using Tail recursive

## C++

 `#include ``using` `namespace` `std;`` ` `int` `Multi_Two(``int` `value)``{``    ``int` `result = 0;``    ``for` `(``int` `i = 0; i < value; ++i) {``        ``result += 2;``    ``}`` ` `    ``    ``return` `result;``}`` ` `int` `main()``{``    ``int` `N = 34;`` ` `    ``    ``cout << Multi_Two(N);``    ``return` `0;``}`

Time Complexity: O(N)
Auxiliary Space: O(1)

Source: www.geeksforgeeks.org