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
void print(int n)
{
if (n < 0)
return;
printf("%d ", n);
print(n - 1);
}
|
C++
static void print(int n)
{
if (n < 0)
return;
cout << " " << n;
print(n - 1);
}
|
Java
static void print(int n)
{
if (n < 0)
return;
System.out.print(" " + n);
print(n - 1);
}
|
Python3
def prints(n):
if (n < 0):
return
print(str(n), end=' ')
prints(n-1)
|
C#
static void print(int n)
{
if (n < 0)
return;
Console.Write(" " + n);
print(n - 1);
}
|
Javascript
<script>
function print(n)
{
if (n < 0)
return;
document.write(" " + n);
print(n - 1);
}
</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;
unsigned int fact(unsigned int n)
{
if (n <= 0)
return 1;
return n * fact(n - 1);
}
int main()
{
cout << fact(5);
return 0;
}
|
Java
class GFG {
static int fact(int n)
{
if (n == 0)
return 1;
return n * fact(n - 1);
}
public static void main(String[] args)
{
System.out.println(fact(5));
}
}
|
Python3
def fact(n):
if (n == 0):
return 1
return n * fact(n-1)
if __name__ == '__main__':
print(fact(5))
|
C#
using System;
class GFG {
static int fact(int n)
{
if (n == 0)
return 1;
return n * fact(n - 1);
}
public static void Main() { Console.Write(fact(5)); }
}
|
PHP
<?php
function fact( $n)
{
if ($n == 0) return 1;
return $n * fact($n - 1);
}
echo fact(5);
?>
|
Javascript
<script>
function fact(n)
{
if (n == 0)
return 1;
return n * fact(n - 1);
}
document.write(fact(5));
</script>
|
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;
unsigned factTR(unsigned int n, unsigned int a)
{
if (n <= 1)
return a;
return factTR(n - 1, n * a);
}
unsigned int fact(unsigned int n) { return factTR(n, 1); }
int main()
{
cout << fact(5);
return 0;
}
|
Java
class GFG {
static int factTR(int n, int a)
{
if (n <= 0)
return a;
return factTR(n - 1, n * a);
}
static int fact(int n) { return factTR(n, 1); }
static public void main(String[] args)
{
System.out.println(fact(5));
}
}
|
Python3
def fact(n, a=1):
if (n <= 1):
return a
return fact(n - 1, n * a)
print(fact(5))
|
C#
using System;
class GFG {
static int factTR(int n, int a)
{
if (n <= 0)
return a;
return factTR(n - 1, n * a);
}
static int fact(int n) { return factTR(n, 1); }
static public void Main()
{
Console.WriteLine(fact(5));
}
}
|
PHP
<?php
function factTR($n, $a)
{
if ($n <= 0) return $a;
return factTR($n - 1, $n * $a);
}
function fact($n)
{
return factTR($n, 1);
}
echo fact(5);
?>
|
Javascript
<script>
function factTR(n, a)
{
if (n <= 0)
return a;
return factTR(n - 1, n * a);
}
function fact(n)
{
return factTR(n, 1);
}
document.write(fact(5));
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)
Next articles on this topic:
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
