What is a Proper Tail Call?

View Discussion

Improve Article

Save Article

Like Article

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 <bits/stdc++.h>

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 <bits/stdc++.h>

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)

By Julio MarchiPosted on