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)
Need for Tail Recursion:
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).
Can a non-tail-recursive function be written as tail-recursive to optimize it?
Consider the following function to calculate the factorial of n.
It is a non-tail-recursive function. Although it looks like a tail recursive at first look. If we take a closer look, we can see that the value returned by fact(n-1) is used in fact(n). So the call to fact(n-1) is not the last thing done by fact(n).
C++
#include <iostream> using namespace std; // A NON-tail-recursive function. The function is not tail // recursive because the value returned by fact(n-1) is used // in fact(n) and call to fact(n-1) is not the last thing // done by fact(n) unsigned int fact(unsigned int n) { if (n <= 0) return 1; return n * fact(n - 1); } // Driver program to test above function int main() { cout << fact(5); return 0; } |
Java
class GFG { // A NON-tail-recursive function. // The function is not tail // recursive because the value // returned by fact(n-1) is used // in fact(n) and call to fact(n-1) // is not the last thing done by // fact(n) static int fact( int n) { if (n == 0 ) return 1 ; return n * fact(n - 1 ); } // Driver program public static void main(String[] args) { System.out.println(fact( 5 )); } } // This code is contributed by Smitha. |
Python3
# A NON-tail-recursive function. # The function is not tail # recursive because the value # returned by fact(n-1) is used # in fact(n) and call to fact(n-1) # is not the last thing done by # fact(n) def fact(n): if (n = = 0 ): return 1 return n * fact(n - 1 ) # Driver program to test # above function if __name__ = = '__main__' : print (fact( 5 )) # This code is contributed by Smitha. |
C#
using System; class GFG { // A NON-tail-recursive function. // The function is not tail // recursive because the value // returned by fact(n-1) is used // in fact(n) and call to fact(n-1) // is not the last thing done by // fact(n) static int fact( int n) { if (n == 0) return 1; return n * fact(n - 1); } // Driver program to test // above function public static void Main() { Console.Write(fact(5)); } } // This code is contributed by Smitha |
PHP
<?php // A NON-tail-recursive function. // The function is not tail // recursive because the value // returned by fact(n-1) is used in // fact(n) and call to fact(n-1) is // not the last thing done by fact(n) function fact( $n ) { if ( $n == 0) return 1; return $n * fact( $n - 1); } // Driver Code echo fact(5); // This code is contributed by Ajit ?> |
Javascript
<script> // A NON-tail-recursive function. // The function is not tail // recursive because the value // returned by fact(n-1) is used // in fact(n) and call to fact(n-1) // is not the last thing done by // fact(n) function fact(n) { if (n == 0) return 1; return n * fact(n - 1); } // Driver code document.write(fact(5)); // This code is contributed by divyeshrabadiya07 </script> |
120
Time Complexity: O(n)
Auxiliary Space: O(n)
The above function can be written as a tail-recursive function. The idea is to use one more argument and accumulate the factorial value in the second argument. When n reaches 0, return the accumulated value.
Below is the implementation using a tail-recursive function.
C++
#include <iostream> using namespace std; // A tail recursive function to calculate factorial unsigned factTR(unsigned int n, unsigned int a) { if (n <= 1) return a; return factTR(n - 1, n * a); } // A wrapper over factTR unsigned int fact(unsigned int n) { return factTR(n, 1); } // Driver program to test above function int main() { cout << fact(5); return 0; } |
Java
// Java Code for Tail Recursion class GFG { // A tail recursive function // to calculate factorial static int factTR( int n, int a) { if (n <= 0 ) return a; return factTR(n - 1 , n * a); } // A wrapper over factTR static int fact( int n) { return factTR(n, 1 ); } // Driver code static public void main(String[] args) { System.out.println(fact( 5 )); } } // This code is contributed by Smitha. |
Python3
# A tail recursive function # to calculate factorial def fact(n, a = 1 ): if (n < = 1 ): return a return fact(n - 1 , n * a) # Driver program to test # above function print (fact( 5 )) # This code is contributed # by Smitha # improved by Ujwal, ashish2021 |
C#
// C# Code for Tail Recursion using System; class GFG { // A tail recursive function // to calculate factorial static int factTR( int n, int a) { if (n <= 0) return a; return factTR(n - 1, n * a); } // A wrapper over factTR static int fact( int n) { return factTR(n, 1); } // Driver code static public void Main() { Console.WriteLine(fact(5)); } } // This code is contributed by Ajit. |
PHP
<?php // A tail recursive function // to calculate factorial function factTR( $n , $a ) { if ( $n <= 0) return $a ; return factTR( $n - 1, $n * $a ); } // A wrapper over factTR function fact( $n ) { return factTR( $n , 1); } // Driver program to test // above function echo fact(5); // This code is contributed // by Smitha ?> |
Javascript
<script> // Javascript Code for Tail Recursion // A tail recursive function // to calculate factorial function factTR(n, a) { if (n <= 0) return a; return factTR(n - 1, n * a); } // A wrapper over factTR function fact(n) { return factTR(n, 1); } // Driver code document.write(fact(5)); // This code is contributed by rameshtravel07 </script> |
120
Time Complexity: O(n)
Auxiliary Space: O(1)
Next articles on this topic:
Contact Us