Tail Recursion

# Tail Recursion Notes | Study Programming and Data Structures - Computer Science Engineering (CSE)

## Document Description: Tail Recursion for Computer Science Engineering (CSE) 2022 is part of Programming and Data Structures preparation. The notes and questions for Tail Recursion have been prepared according to the Computer Science Engineering (CSE) exam syllabus. Information about Tail Recursion covers topics like and Tail Recursion Example, for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises and tests below for Tail Recursion.

Introduction of Tail Recursion in English is available as part of our Programming and Data Structures for Computer Science Engineering (CSE) & Tail Recursion in Hindi for Programming and Data Structures course. Download more important topics related with notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Computer Science Engineering (CSE): Tail Recursion Notes | Study Programming and Data Structures - Computer Science Engineering (CSE)
 1 Crore+ students have signed up on EduRev. Have you?

What is tail recursion?

A recursive function is tail recursive when recursive call is the last thing executed by the function. 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;
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);
}
// 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

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

Why do we care?

The tail recursive functions considered better than non tail recursive functions as tail-recursion can be optimized by compiler. 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 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
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>

Output :
120

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 second argument. When n reaches 0, return the accumulated value.

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));
}
}
// This code is contributed by Smitha.

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))
# This code is contributed
# by Smitha
# "improved by Ujwal"

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>

Output :
120

The document Tail Recursion Notes | Study Programming and Data Structures - Computer Science Engineering (CSE) is a part of the Computer Science Engineering (CSE) Course Programming and Data Structures.
All you need of Computer Science Engineering (CSE) at this link: Computer Science Engineering (CSE)

## Programming and Data Structures

56 docs|16 tests
 Use Code STAYHOME200 and get INR 200 additional OFF

## Programming and Data Structures

56 docs|16 tests

Track your progress, build streaks, highlight & save important lessons and more!

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;