Tail Recursion - Programming and Data Structures - Computer Science Engineering

What is Tail Recursion?

A recursive function is tail recursive when the recursive call is the last statement executed by the function. This means that after the recursive call is made, there are no further operations or computations to be performed. In other words, the function immediately returns the result of the recursive call without any additional processing.

Consider the following example of a tail recursive function that prints numbers from n down to 0:

Tail Recursive Function Example

C++

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

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);
}

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)

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);
}

In all these examples, the recursive call print(n - 1) is the last statement in the function. No computation happens after this call returns. This is the defining characteristic of tail recursion.

Why is Tail Recursion Important?

Tail recursive functions can be more memory efficient in languages or compilers that support tail call optimization (TCO). However, not all languages or compilers guarantee this optimization. The optimisation technique is called tail call optimisation or tail call elimination.

The reason behind this optimisation is straightforward: since the recursive call is the last statement executed in the function, there is nothing left to do after the function returns. Therefore, saving the current function's stack frame on the call stack is unnecessary. The compiler or runtime system can reuse the same stack frame for the next recursive call instead of creating a new one. This way, the function consumes constant stack space instead of linear stack space, which prevents stack overflow for deep recursion and improves memory efficiency.

Without tail call optimisation, each recursive call creates a new stack frame, and these frames accumulate until the base case is reached. This uses O(n) memory for n recursive calls. With tail call optimisation, the same stack frame is reused, using only O(1) memory regardless of the depth of recursion.

Note: Tail call optimization depends on the language/compiler implementation. Python, for example, does not perform tail call optimization, so tail-recursive Python functions still use O(n) stack space.

Converting Non-Tail Recursive Functions to Tail Recursive Functions

Not all recursive functions are naturally tail recursive. However, many non-tail recursive functions can be rewritten as tail recursive functions. Let us examine the factorial function, which is a classic example of a non-tail recursive function, and then see how it can be converted to a tail recursive function.

Non-Tail Recursive Factorial Function

Consider the following function to calculate the factorial of 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));
}
}

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
print(fact(5))

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));
}
}

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);
?>

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));
</script>

Output:

120

This function is not tail recursive. Although the recursive call occurs near the end of the return statement, the multiplication must still be performed after the recursive call returns. The multiplication n * fact(n-1) is the last operation performed by the function, not the recursive call itself. Therefore, the compiler cannot optimise this function using tail call optimisation.

Converting to Tail Recursive Factorial Function

The key idea to convert a non-tail recursive function to a tail recursive function is to introduce an additional parameter called an accumulator. This accumulator holds the intermediate result of the computation and is passed along with each recursive call. When the base case is reached, we simply return the accumulated value without any further computation.

The factorial function can be rewritten as a tail recursive function by using an accumulator parameter:

C++

#include <iostream>
using namespace std;
// A tail recursive function to calculate factorial
unsigned factTR(unsigned int n, unsigned int a)
{
if (n == 0)
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));
}
}

Python3

# A tail recursive function to calculate factorial
def fact(n, a=1):
if (n == 0):
return a
return fact(n - 1, n * a)
# Driver program to test above function
print(fact(5))

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));
}
}

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);
?>

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));
</script>

Output:

120

In this tail recursive version, the function factTR uses an accumulator parameter a to store the running product. The function now makes the recursive call as its last statement: return factTR(n - 1, n * a). The multiplication happens before the recursive call, not after it. This means the recursive call is truly the last operation, making this function tail recursive.

The wrapper function fact initialises the accumulator to 1 (the multiplicative identity for factorials) and calls the tail recursive function. This separation allows us to maintain a clean interface while leveraging tail call optimisation internally.

When fact(5) is called, the execution proceeds as follows: the accumulator steadily accumulates the product as we count down from 5 to 0. Once n reaches 0, the function simply returns the accumulated value 120, which is the factorial of 5. The compiler can optimise this by reusing the same stack frame for each call, avoiding the creation of multiple stack frames and thus preventing stack overflow for large values of n.