Sunday, April 2, 2023
HomeSoftware DevelopmentWhat is a Proper Tail Call?

# What is a Proper Tail Call?

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)

RELATED ARTICLES