What do you mean by Stack?

A Stack is a widely used linear data structure in modern computers in

which insertions and deletions of an element can occur only at one
end, i.e., top of the Stack. It is used in all those applications in which
data must be stored and retrieved in the last.

An everyday analogy of a stack data structure is a stack of books on a

desk, Stack of plates, table tennis, Stack of bootless, Undo or Redo
mechanism in the Text Editors, etc.

What is a Stack?
A Stack is a linear data structure that follows the LIFO (Last-In-
First-Out) principle. Stack has one end, whereas the Queue has two
ends (front and rear). It contains only one pointer top
pointer pointing to the topmost element of the stack. Whenever an
element is added in the stack, it is added on the top of the stack, and
the element can be deleted only from the stack. In other words,
a stack can be defined as a container in which insertion and
deletion can be done from the one end known as the top of the
stack.
Stack underflow
happens when we try to pop (remove) an item from the stack,
when nothing is actually there to remove. This will raise an alarm
of sorts in the computer because we told it to do something that
cannot be done.
Stack overflow
happens when we try to push one more item onto our stack than it
can actually hold. You see, the stack usually can hold only so
much stuff. Typically, we allocate (set aside) where the stack is
going to be in memory and how big it can get. So, when we stick
too much stuff there or try to remove nothing, we will generate a
stack overflow condition or stack underflow condition,
respectively.

Some key points related to stack

o It is called as stack because it behaves like a real-world stack, piles of
books, etc.
o A Stack is an abstract data type with a pre-defined capacity, which means
that it can store the elements of a limited size.
o It is a data structure that follows some order to insert and delete the
elements, and that order can be LIFO or FILO.

Working of Stack
Stack works on the LIFO pattern. As we can observe in the below
figure there are five memory blocks in the stack; therefore, the size of
the stack is 5.

Suppose we want to store the elements in a stack and let's assume that
stack is empty. We have taken the stack of size 5 as shown below in
which we are pushing the elements one by one until the stack
becomes full.
Since our stack is full as the size of the stack is 5. In the above cases, we can
observe that it goes from the top to the bottom when we were entering the new
element in the stack. The stack gets filled up from the bottom to the top.

When we perform the delete operation on the stack, there is only one
way for entry and exit as the other end is closed. It follows the LIFO
pattern, which means that the value entered first will be removed last.
In the above case, the value 5 is entered first, so it will be removed
only after the deletion of all the other elements.

Standard Stack Operations

The following are some common operations implemented on the
stack:

o push(): When we insert an element in a stack then the operation is known

as a push. If the stack is full then the overflow condition occurs.
o pop(): When we delete an element from the stack, the operation is known
as a pop. If the stack is empty means that no element exists in the stack,
this state is known as an underflow state.
o isEmpty(): It determines whether the stack is empty or not.
o isFull(): It determines whether the stack is full or not.'
o peek(): It returns the element at the given position.
o count(): It returns the total number of elements available in a stack.
o change(): It changes the element at the given position.
o display(): It prints all the elements available in the stack.
PUSH operation
The steps involved in the PUSH operation is given below:

o Before inserting an element in a stack, we check whether the stack is full.

o If we try to insert the element in a stack, and the stack is full, then
the overflow condition occurs.
o When we initialize a stack, we set the value of top as -1 to check that the
stack is empty.
o When the new element is pushed in a stack, first, the value of the top gets
incremented, i.e., top=top+1, and the element will be placed at the new
position of the top.
o The elements will be inserted until we reach the max size of the stack.

POP operation
The steps involved in the POP operation is given below:

o Before deleting the element from the stack, we check whether the stack is
empty.
o If we try to delete the element from the empty stack, then
the underflow condition occurs.
 o If the stack is not empty, we first access the element which is pointed by
the top
o Once the pop operation is performed, the top is decremented by 1,
i.e., top=top-1.
o

The way to write arithmetic expression is known as a notation. An

arithmetic expression can be written in three different but equivalent
notations, i.e., without changing the essence or output of an
expression. These notations are −
 Infix Notation
 Prefix (Polish) Notation
 Postfix (Reverse-Polish) Notation
These notations are named as how they use operator in expression.
We shall learn the same here in this chapter.
Infix Notation
We write expression in infix notation, e.g. a - b + c, where operators
are used in-between operands. It is easy for us humans to read, write,
and speak in infix notation but the same does not go well with
computing devices. An algorithm to process infix notation could be
difficult and costly in terms of time and space consumption.
Prefix Notation
In this notation, operator is prefixed to operands, i.e. operator is
written ahead of operands. For example, +ab. This is equivalent to its
infix notation a + b. Prefix notation is also known as Polish Notation.
Postfix Notation
This notation style is known as Reversed Polish Notation. In this
notation style, the operator is postfixed to the operands i.e., the
operator is written after the operands. For example, ab+. This is
equivalent to its infix notation a + b.
The following table briefly tries to show the difference in all three
notations −
[Link]. Infix Notation Prefix Notation Postfix Notation

1 a+b +ab ab+

2 (a + b) ∗ c ∗+abc ab+c∗

3 a ∗ (b + c) ∗a+bc abc+∗

4 a/b+c/d +/ab/cd ab/cd/+

5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗

6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-

Parsing Expressions
As we have discussed, it is not a very efficient way to design an
algorithm or program to parse infix notations. Instead, these infix
notations are first converted into either postfix or prefix notations and
then computed.
To parse any arithmetic expression, we need to take care of operator
precedence and associativity also.
Precedence
When an operand is in between two different operators, which
operator will take the operand first, is decided by the precedence of an
operator over others. For example −

As multiplication operation has precedence over addition, b * c will

be evaluated first. A table of operator precedence is provided later.
Associativity
Associativity describes the rule where operators with the same
precedence appear in an expression. For example, in expression a + b
− c, both + and – have the same precedence, then which part of the
expression will be evaluated first, is determined by associativity of
those operators. Here, both + and − are left associative, so the
expression will be evaluated as (a + b) − c.
Precedence and associativity determines the order of evaluation of an
expression. Following is an operator precedence and associativity
table (highest to lowest) −
[Link]. Operator Precedence Associativity

1 Exponentiation ^ Highest Right Associativ

2 Multiplication ( ∗ ) & Division ( / ) Second Highest Left Associative

3 Addition ( + ) & Subtraction ( − ) Lowest Left Associative

The above table shows the default behavior of operators. At any point
of time in expression evaluation, the order can be altered by using
parenthesis. For example −
In a + b*c, the expression part b*c will be evaluated first, with
multiplication as precedence over addition. We here use parenthesis
for a + b to be evaluated first, like (a + b)*c.

1. PUSH: PUSH operation implies the insertion of a new element into a Stack. A new
element is always inserted from the topmost position of the Stack; thus, we always need to
check if the top is empty or not, i.e., TOP=Max-1 if this condition goes false, it means the
Stack is full, and no more elements can be inserted, and even if we try to insert the element, a
Stack overflow message will be displayed.
Algorithm:
Step-1: If TOP = Max-1
Print “Overflow”
Goto Step 4
Step-2: Set TOP= TOP + 1
Step-3: Set Stack[TOP]= ELEMENT
Step-4: END

2. POP: POP means to delete an element from the Stack. Before deleting an element, make
sure to check if the Stack Top is NULL, i.e., TOP=NULL. If this condition goes true, it
means the Stack is empty, and no deletion operation can be performed, and even if we try to
delete, then the Stack underflow message will be generated.
Algorithm:
Step-1: If TOP= NULL
Print “Underflow”
Goto Step 4
Step-2: Set VAL= Stack[TOP]
Step-3: Set TOP= TOP-1
Step-4: END

3. PEEK: When we need to return the value of the topmost element of the Stack without
deleting it from the Stack, the Peek operation is used. This operation first checks if the Stack
is empty, i.e., TOP = NULL; if it is so, then an appropriate message will display, else the
value will return.
Algorithm:
Step-1: If TOP = NULL
PRINT “Stack is Empty”
Goto Step 3
Step-2: Return Stack[TOP]
Step-3: END

Application of Stack in real life:

 CD/DVD stand.
 Stack of books in a book shop.
 Undo and Redo mechanism in text editors.
 The history of a web browser is stored in the form of a stack.
 Call logs, E-mails, and Google photos in any gallery are also
stored in form of a stack.
 YouTube downloads and Notifications are also shown in
LIFO format(the latest appears first ).
Advantages of Stack:
 Stack helps in managing data that follows the LIFO
technique.
 Stacks are be used for systematic Memory Management.
 It is used in many virtual machines like JVM.
 When a function is called, the local variables and other
function parameters are stored in the stack and automatically
destroyed once returned from the function. Hence, efficient
function management.
 Stacks are more secure and reliable as they do not get
corrupted easily.
 Stack allows control over memory allocation and
deallocation.
 Stack cleans up the objects automatically.
Disadvantages of Stack:
 Stack memory is of limited size.
  The total of size of the stack must be defined before.
 If too many objects are created then it can lead to stack
overflow.
 Random accessing is not possible in stack.
 If the stack falls outside the memory it can lead to abnormal
termination.

Applications of Stack in Data Structure:

 1. Expression Evaluation and Conversion

 2. Backtracking

 3. Parenthesis Checking

 4. Function Call

 5. String Reversal

 6. Syntax Parsing

 7. Memory Management

1. Expression Evaluation and Conversion

There are 3 types of expression we use in Programming, which are
Infix Expression, Prefix Expression and Postfix Expression.

Infix Expression is represented as X + Y. Prefix Expression is

represented as +XY and Postfix Expression is represented as XY+.

In order to evaluate these expressions in Programming, a Data

Structure called Stack is used.

Similarly, Stack is also used for Converting one expression into

another. For example, converting Infix to Postfix or Infix to Prefix.

2. Backtracking
Backtracking is a recursive algorithm which is used for solving the
optimization problem.
So, In order to find the optimized solution of a problem with
Backtracking, we have to find each and every possible solution of the
problem, doesn’t matter if it is correct or not.

In Backtracking, while finding the every possible solution of a

problem, we store the solution of a previously calculated problem in
Stack and use that solution to solve the upcoming problems.

3. Parenthesis Checking
In Programming, we make use of different type of parenthesis, like –
(, ), {, }, which are used for opening and closing a block of code.

So, these parenthesis get stored in Stack and control the flow of our
program.

4. Function Call
In Programming, whenever you make a call from one function to the
another function. The address of the calling function gets stored in the
Stack.

So, when the called function gets terminated. The program control
move back to the calling function with the help of the address which
was stored in the Stack.

So, Stack plays the main role when it comes to Calling a Function
from other Function.

5. String Reversal
String Reversal is another amazing Application of Stack. Here, one by
one each character of the Stack get inserted into the Stack.

So, the first character of the Stack is on the bottom of the Stack and
the last character of the String is on the Top of the Stack.

After performing the pop operation in Stack, we get the String in

Reverse order.
6. Syntax Parsing
As many of the Programming Languages are context-free languages.
So, Stack is also heavily used for Syntax Parsing by most of the
Compilers.
7. Memory Management
Memory Management is the important function of the Operating
System. Stack also plays the main role when it comes to Memory
Management.

Arithmetic Expression Evaluation
The stack organization is very effective in evaluating arithmetic
expressions. Expressions are usually represented in what is known
as Infix notation, in which each operator is written between two
operands (i.e., A + B). With this notation, we must distinguish
between ( A + B )*C and A + ( B * C ) by using either parentheses or
some operator-precedence convention. Thus, the order of operators
and operands in an arithmetic expression does not uniquely
determine the order in which the operations are to be performed.
1. Polish notation (prefix notation) –
It refers to the notation in which the operator is placed before its two
operands. Here no parentheses are required, i.e.,

+AB

2. Reverse Polish notation(postfix notation) –

It refers to the analogous notation in which the operator is placed
after its two operands. Again, no parentheses is required in Reverse
Polish notation, i.e.,

AB+
Stack-organized computers are better suited for post-fix notation
than the traditional infix notation. Thus, the infix notation must be
converted to the postfix notation. The conversion from infix notation
to postfix notation must take into consideration the operational
hierarchy.
There are 3 levels of precedence for 5 binary operators as given
below:

Highest: Exponentiation (^)

Next highest: Multiplication (*) and division (/)
Lowest: Addition (+) and Subtraction (-)
For example –

Infix notation: (A-B)*[C/(D+E)+F]

Post-fix notation: AB- CDE +/F +*
Here, we first perform the arithmetic inside the parentheses (A-B)
and (D+E). The division of C/(D+E) must be done prior to the
addition with F. After that multiply the two terms inside the
parentheses and bracket.
Now we need to calculate the value of these arithmetic operations by
using a stack.
The procedure for getting the result is:

1. Convert the expression in Reverse Polish notation( post-fix

notation).

2. Push the operands into the stack in the order they appear.

3. When any operator encounters then pop two topmost

operands for executing the operation.

4. After execution push the result obtained into the stack.

5. After the complete execution of expression, the final result

remains on the top of the stack.

For example –

Infix notation: (2+4) * (4+6)

Post-fix notation: 2 4 + 4 6 + *
Result: 60
The stack operations for this expression evaluation is shown below:
What is Balance Parenthesis Problem?
First we get the string as an input containing the characters (', ')', '{',
'}', '[', and ']', to check if the given string is valid or not.

BALANCE PARENTHESIS

We now turn our attention to using stacks to solve real computer

science problems. You’ve no doubt written arithmetic expressions
such as

(5+6)\times(7+8)/(4+3)(5+6)×(7+8)/(4+3)
where parentheses are used to order the performance of operations.
You may also have some experience programming in a language such
as Lisp with constructs like
(defun square(n)
(* n n))

This defines a function called square that will return the square of its
argument n. Lisp is notorious for using lots and lots of parentheses.

In both of these examples, parentheses must appear in a balanced

fashion. Balanced parentheses means that each opening symbol has a
corresponding closing symbol and the pairs of parentheses are
properly nested. Consider the following correctly balanced strings of
parentheses:
(()()()())

(((())))

(()((())()))

Compare those with the following, which aren’t balanced:

((((((())
()))

(()()(()

The ability to differentiate between parentheses that are correctly

balanced and those that are unbalanced is an important part of
recognizing many programming language structures.

The challenge then is to write an algorithm that will read a string of

parentheses from left to right and decide whether the symbols are
balanced. To solve this problem we need to make an important
observation. As you process symbols from left to right, the most
recent opening parenthesis must match the next closing symbol. Also,
the first opening symbol processed may have to wait until the very
last symbol for its match. Closing symbols match opening symbols in
the reverse order of their appearance; they match from the inside out.
This is a clue that stacks can be used to solve the problem.

Matching parentheses

Once you agree that a stack is the appropriate data structure for
keeping the parentheses, the statement of the algorithm is
straightforward. Starting with an empty stack, process the parenthesis
strings from left to right. If a symbol is an opening parenthesis, push it
on the stack as a signal that a corresponding closing symbol needs to
appear later. If, on the other hand, a symbol is a closing parenthesis,
pop the stack. As long as it’s possible to pop the stack to match every
closing symbol, the parentheses remain balanced. If at any time
there’s no opening symbol on the stack to match a closing symbol, the
string is not balanced properly. At the end of the string, when all
symbols have been processed, the stack should be empty. The Python
code to implement this algorithm may look like this:
OPENING = '('
def is_balanced(parentheses):
stack = []
for paren in parentheses:
if paren == OPENING:
[Link](paren)
else:
try:
[Link]()
except IndexError: # too many closing parens
return False
return len(stack) == 0 # false if too many opening parens

is_balanced('((()))') # => True

is_balanced('(()') # => False
is_balanced('())') # => False

This function, is_balanced, returns a boolean result as to whether the

string of parentheses is balanced. If the current symbol is (, then it’s
pushed on the stack. If it is ) we attempt to pop from the stack. If the
stack is empty at that point, we know that the parenthesis string is
imbalanced with too many closing parens. Finally, as long as the
expression is balanced and the stack has been completely cleaned off,
the string represents a correctly balanced sequence of parentheses.

Balanced Symbols: A General Case

The balanced parentheses problem shown above is a specific case of a

more general situation that arises in many programming languages.
The general problem of balancing and nesting different kinds of
opening and closing symbols occurs frequently. For example, in
Python square brackets, [ and ], are used for lists; curly braces, { and },
are used for dictionaries; and parentheses, ( and ), are used for tuples
and arithmetic expressions. It’s possible to mix symbols as long as
each maintains its own open and close relationship. Strings of
symbols such as
{{([][])}()}

[[{{(())}}]]

[][][](){}
are properly balanced in that not only does each opening symbol have
a corresponding closing symbol, but the types of symbols match as
well.

Compare those with the following strings that are not balanced:
([)]

((()]))

[{()]

The simple parentheses checker from the previous section can easily
be extended to handle these new types of symbols. Recall that each
opening symbol is simply pushed on the stack to wait for the
matching closing symbol to appear later in the sequence. When a
closing symbol does appear, the only difference is that we must check
to be sure that it correctly matches the type of the opening symbol on
top of the stack. If the two symbols don’t match, the string isn’t
balanced. Once again, if the entire string is processed and nothing is
left on the stack, the string is correctly balanced.

The Python program to implement this is shown below. The only

change is that we use a dictionary to ensure that symbols popped from
the stack correctly match our expectations of pairing with the symbol
being considered at the time.
PAIRINGS = {
'(': ')',
'{': '}',
'[': ']'
}

def is_balanced(symbols):
stack = []
for s in symbols:
if s in PAIRINGS:
[Link](s)
 continue
try:
expected_opening_symbol = [Link]()
except IndexError: # too many closing symbols
return False
if s != PAIRINGS[expected_opening_symbol]: # mismatch
return False
return len(stack) == 0 # false if too many opening symbols

is_balanced('{{([][])}()}') # => True

is_balanced('{[])') # => False
is_balanced('((()))') # => True
is_balanced('(()') # => False
is_balanced('())') # => False

These two examples show that stacks are very important data
structures for the processing of language constructs in computer
science. Almost any notation you can think of has some type of nested
symbol that must be matched in a balanced order. There are a number
of other important uses for stacks in computer science. We’ll continue
to explore them in the next sections.

Check for balanced parentheses in

Python
Given an expression string, write a python program to find whether a
given string has balanced parentheses or not.
Examples:
Input : {[]{()}}
Output : Balanced

Input : [{}{}(]
Output : Unbalanced
Approach #1 : Using stack
One approach to check balanced parentheses is to use stack. Each
time, when an open parentheses is encountered push it in the stack,
and when closed parenthesis is encountered, match it with the top of
stack and pop it. If stack is empty at the end, return Balanced
otherwise, Unbalanced.
 # Python3 code to Check for
# balanced parentheses in an expression
open_list = ["[","{","("]
close_list = ["]","}",")"]

# Function to check parentheses

def check(myStr):
stack = []
for i in myStr:
if i in open_list:
[Link](i)
elif i in close_list:
pos = close_list.index(i)
if ((len(stack) > 0) and
(open_list[pos] == stack[len(stack)-1])):
[Link]()
else:
return "Unbalanced"
if len(stack) == 0:
return "Balanced"
else:
return "Unbalanced"

# Driver code
string = "{[]{()}}"
print(string,"-", check(string))

string = "[{}{})(]"
print(string,"-", check(string))

string = "((()"
print(string,"-",check(string))

Output:
{[]{()}} - Balanced
[{}{})(] - Unbalanced
((() – Unbalanced
What is Recursion?
The process in which a function calls itself directly or indirectly is
called recursion and the corresponding function is called a recursive
function. Using a recursive algorithm, certain problems can be
solved quite easily. Examples of such problems are Towers of Hanoi
(TOH), Inorder/Preorder/Postorder Tree Traversals , DFS of Graph,
etc. A recursive function solves a particular problem by calling a
copy of itself and solving smaller subproblems of the original
problems. Many more recursive calls can be generated as and when
required. It is essential to know that we should provide a certain case
in order to terminate this recursion process. So we can say that every
time the function calls itself with a simpler version of the original
problem.
Need of Recursion
Recursion is an amazing technique with the help of which we can
reduce the length of our code and make it easier to read and write. It
has certain advantages over the iteration technique which will be
discussed later. A task that can be defined with its similar subtask,
recursion is one of the best solutions for it. For example; The
Factorial of a number.
Properties of Recursion:
 Performing the same operations multiple times with different
inputs.
 In every step, we try smaller inputs to make the problem
smaller.
 Base condition is needed to stop the recursion otherwise
infinite loop will occur.
A Mathematical Interpretation
Let us consider a problem that a programmer has to determine the
sum of first n natural numbers, there are several ways of doing that
but the simplest approach is simply to add the numbers starting from
1 to n. So the function simply looks like this,
approach(1) – Simply adding one by one
f(n) = 1 + 2 + 3 +……..+ n
but there is another mathematical approach of representing this,
approach(2) – Recursive adding
f(n) = 1 n=1
f(n) = n + f(n-1) n>1
There is a simple difference between the approach (1) and
approach(2) and that is in approach(2) the function “ f( ) ” itself is
being called inside the function, so this phenomenon is named
recursion, and the function containing recursion is called recursive
function, at the end, this is a great tool in the hand of the
programmers to code some problems in a lot easier and efficient
way.
How are recursive functions stored in memory?
Recursion uses more memory, because the recursive function adds to
the stack with each recursive call, and keeps the values there until
the call is finished. The recursive function uses LIFO (LAST IN
FIRST OUT) Structure just like the stack data
structure. [Link]

What is the base condition in recursion?

In the recursive program, the solution to the base case is provided
and the solution to the bigger problem is expressed in terms of
smaller problems.

int fact(int n)
{
if (n < = 1) // base case
return 1;
else
return n*fact(n-1);
}
In the above example, the base case for n < = 1 is defined and the
larger value of a number can be solved by converting to a smaller
one till the base case is reached.
How a particular problem is solved using recursion?
The idea is to represent a problem in terms of one or more smaller
problems, and add one or more base conditions that stop the
recursion. For example, we compute factorial n if we know the
factorial of (n-1). The base case for factorial would be n = 0. We
return 1 when n = 0.
Why Stack Overflow error occurs in recursion?
If the base case is not reached or not defined, then the stack overflow
problem may arise. Let us take an example to understand this.
int fact(int n)
{
// wrong base case (it may cause
// stack overflow).
if (n == 100)
return 1;

else
return n*fact(n-1);
}
If fact(10) is called, it will call fact(9), fact(8), fact(7), and so on but
the number will never reach 100. So, the base case is not reached. If
the memory is exhausted by these functions on the stack, it will
cause a stack overflow error.
What is the difference between direct and indirect recursion?
A function fun is called direct recursive if it calls the same function
fun. A function fun is called indirect recursive if it calls another
function say fun_new and fun_new calls fun directly or indirectly.
The difference between direct and indirect recursion has been
illustrated in Table 1.
// An example of direct recursion
void directRecFun()
{
 // Some code....

directRecFun();

// Some code...
}

// An example of indirect recursion

void indirectRecFun1()
{
// Some code...

indirectRecFun2();

// Some code...
}
void indirectRecFun2()
{
// Some code...

indirectRecFun1();

// Some code...
}

What is Recursion?
The process in which a function calls itself directly or indirectly is
called recursion and the corresponding function is called a recursive
function. Using recursive algorithm, certain problems can be solved
quite easily. Examples of such problems are Towers of Hanoi
(TOH), Inorder/Preorder/Postorder Tree Traversals , DFS of Graph,
etc.
Types of Recursions:
1. Direct Recursion
2. Indirect Recursion
3. Tail Recursion
4. No Tail/ Head Recursion
Recursion are mainly of two types depending on whether a function
calls itself from within itself or more than one function call one
another mutually. The first one is called direct recursion and
another one is called indirect recursion. Thus, the two types of
recursion are:
1. Direct Recursion: These can be further categorized into four
types:
Tail Recursion: If a recursive function calling itself and that
recursive call is the last statement in the function then it’s known
as Tail Recursion. After that call the recursive function performs
nothing. The function has to process or perform any operation at the
time of calling and it does nothing at returning time.
Example: Code Showing Tail Recursion

# Recursion function
def fun(n):
if (n > 0):
print(n, end=" ")
# Last statement in the function
fun(n - 1)

# Driver Code
x=3
fun(x)

2. Indirect Recursion: In this recursion, there may be more than one

functions and they are calling one another in a circular manner.
From the above diagram fun(A) is calling for fun(B), fun(B) is
calling for fun(C) and fun(C) is calling for fun(A) and thus it makes
a cycle.
Example:
Python program to show Indirect Recursion
def funA(n):
if (n > 0):
print("", n, end='')

# Fun(A) is calling fun(B)

funB(n - 1)

def funB( n):

if (n > 1):
print("", n, end='')

# Fun(B) is calling fun(A)

funA(n // 2)

# Driver code
funA(20)
Tail Recursion
A recursive function is called the tail-recursive if the function makes
recursive calling itself, and that recursive call is the last statement
executes by the function. After that, there is no function or statement
is left to call the recursive function.
Non-Tail / Head Recursion
A function is called the non-tail or head recursive if a function makes
a recursive call itself, the recursive call will be the first statement in
the function. It means there should be no statement or operation is
called before the recursive calls. Furthermore, the head recursive does
not perform any operation at the time of recursive calling. Instead, all
operations are done at the return time.

What is Tail-Recursion?
A unique type of recursion where the last procedure of a function is a
recursive call. The recursion may be automated away by performing
the request in the current stack frame and returning the output
instead of generating a new stack frame. The tail-recursion may be
optimized by the compiler which makes it better than non-tail
recursive functions. Is it possible to optimize a program by
making use of a tail-recursive function instead of non-tail
recursive function? Considering the function given below in order
to calculate the factorial of n, we can observe that the function looks
like a tail-recursive at first but it is a non-tail-recursive function. If
we observe closely, we can see that the value returned by
Recur_facto(n-1) is used in Recur_facto(n), so the call to
Recur_facto(n-1) is not the last thing done by Recur_facto(n).
Program to calculate factorial of a number
# using a Non-Tail-Recursive function.

# non-tail recursive function

def Recur_facto(n):

if (n == 0):
return 1

return n * Recur_facto(n-1)

# print the result

print(Recur_facto(6))

Output
720

# Program to calculate factorial of a number

# using a Tail-Recursive function.

# A tail recursive function

def Recur_facto(n, a = 1):

if (n == 0):
return a

return Recur_facto(n - 1, n * a)

# print the result

print(Recur_facto(6))

Output
720