Need for Tail Recursion

Can a non-tail-recursive function be written as tail-recursive to optimize it?

The tail recursive functions are considered better than non-tail recursive functions as tail-recursion can be optimized by the compiler.

Compilers usually execute recursive procedures by using a stack. This stack consists of all the pertinent information, including the parameter values, for each recursive call. When a procedure is called, its information is pushed onto a stack, and when the function terminates the information is popped out of the stack. Thus for the non-tail-recursive functions, the stack depth (maximum amount of stack space used at any time during compilation) is more.

The idea used by compilers to optimize tail-recursive functions is simple, since the recursive call is the last statement, there is nothing left to do in the current function, so saving the current function’s stack frame is of no use (See this for more details).

What is Tail Recursion

Tail recursion is defined as a recursive function in which the recursive call is the last statement that is executed by the function. So basically nothing is left to execute after the recursion call.

For example the following C++ function print() is tail recursive.

C

// An example of tail recursive function
 
void print(int n)
{
    if (n < 0)
        return;
    printf("%d ", n);
 
    // The last executed statement is recursive call
    print(n - 1);
}

C++

// An example of tail recursive function
 
static void print(int n)
{
    if (n < 0)
        return;
    cout << " " << n;
  
    // The last executed statement is recursive call
    print(n - 1);
}
 
// This code is contributed by Aman Kumar

Java

// An example of tail recursive function
 
static void print(int n)
{
    if (n < 0)
        return;
 
    System.out.print(" " + n);
 
    // The last executed statement
    // is recursive call
    print(n - 1);
}
 
// This code is contributed by divyeh072019

Python3

# An example of tail recursive function
 
 
def prints(n):
 
    if (n < 0):
        return
    print(str(n), end=' ')
 
    # The last executed statement is recursive call
    prints(n-1)
 
    # This code is contributed by Pratham76
    # improved by ashish2021

C#

// An example of tail recursive function
 
static void print(int n)
{
    if (n < 0)
        return;
 
    Console.Write(" " + n);
 
    // The last executed statement
    // is recursive call
    print(n - 1);
}
 
// This code is contributed by divyeshrabadiya07

Javascript

<script>
// An example of tail recursive function 
function print(n) 
{ 
    if (n < 0) 
      return; 
    
    document.write(" " + n); 
    
    // The last executed statement 
      // is recursive call 
    print(n - 1); 
} 
 
// This code is contributed by Rajput-Ji
</script>

Time Complexity: O(n)
Auxiliary Space: O(n)

Tags:

#Quick Sort #tail-recursion #Analysis of Algorithms #DSA #Recursion #Recursion