RP Indraprastha Institute of Technology - [RPIIT]

B-Tech 3rd Sem. Subject: Data Structure and Algorithms

Recursion
Recursion is the process in which a function calls itself again and again. It entails decomposing a
challenging issue into more manageable issues and then solving each one again. There must be a
terminating condition to stop such recursive calls. Recursion may also be called the alternative to
iteration.
The recursive function uses the LIFO (LAST IN FIRST OUT) structure just like the stack data
structure.
When it comes to develop a recursive algorithm, we need to break the provided problem statement
into two parts. The base case is the primary, and the recursive step is the second.
 Base Case: The simplest case of a problem is considered as the base case, which consists of a
state and condition that ends the recursive function. When a certain condition is met, this base
case assesses the result.
 Recursive Step: It computes the output by reaching the same function repeatedly but with
smaller or more complex inputs.
Types of Recursion
The four varieties of recursive algorithms are:
 Direct Recursion
If a function continually calls itself in its same function block, then it is commonly known as
direct recursion.

int fun()
{
…
…
int fun();
}

In this programme, there is a method called fun that calls itself in its function definition. We
can therefore refer to it as straight recursive.
 Indirect Recursion
Indirect recursion occurs when a function invokes another function. The primary function is
then called once again from this function.
 int num()
{
…
…
int sum();
}
int sum()
{
…
…
int num();
}

 Tailed Recursion
If a recursive function conducts recursive calling on its own and that recursive call is the
function’s final statement, the function is said to be tail-recursive. After that, there is no
longer a way or phrase to call the recursive function.

int fun(int x)
{
printf(“%d”,x);
fun(x-1);
//Recursive call is last executed statement
}

 Non-Tailed Recursion
If the recursion call isn’t the last thing the function executes, it’s called non-tail recursive.
There is still stuff to evaluate after returning.

int fun(int x)
{
fun(x-1);
printf(“%d”,x);
//Recursive call is not the final implemented statement
 }

Recursion Uses:
Recursion is used in many fields of computer science and mathematics, which includes:
 Searching and sorting algorithms: Recursive algorithms are used to search and sort data
structures like trees and graphs.
 Mathematical calculations: Recursive algorithms are used to solve problems such as factorial,
Fibonacci sequence, etc.
 Compiler design: Recursion is used in the design of compilers to parse and analyze
programming languages.
 Graphics: many computer graphics algorithms, such as fractals and the Mandelbrot set, use
recursion to generate complex patterns.
 Artificial intelligence: recursive neural networks are used in natural language processing,
computer vision, and other AI applications.

Advantages of Recursion:
 Recursion can simplify complex problems by breaking them down into smaller, more
manageable pieces.
 Recursive code can be more readable and easier to understand than iterative code.
 Recursion is essential for some algorithms and data structures.
 Also with recursion, we can reduce the length of code and become more readable and
understandable to the user/ programmer.

Disadvantages of Recursion:
 Recursion can be less efficient than iterative solutions in terms of memory and performance.
 Recursive functions can be more challenging to debug and understand than iterative solutions.
 Recursion can lead to stack overflow errors if the recursion depth is too high.
Properties of Recursion
1. It solves a problem by breaking it down into smaller sub-problems, each of which can be
solved in the same way.
2. A recursive function must have a base case or stopping criteria to avoid infinite recursion.
3. Recursion involves calling the same function within itself, which leads to a call stack.
4. Recursive functions may be less efficient than iterative solutions in terms of memory and
performance.

Applications of Recursion
1. Recursive solutions are best suited to some problems like:
1. Tree Traversals: InOrder, PreOrder, PostOrder
2. Graph Traversals: DFS [Depth First Search] and BFS [Breadth First Search]
3. Tower of Hanoi
4. Backtracking Algorithms
5. Divide and Conquer Algorithms
6. Dynamic Programming Problems
7. Merge Sort, Quick Sort
8. Binary Search
9. Fibonacci Series, Factorial, etc.
2. Recursion is used in the design of compilers to parse and analyze programming languages.
3. Many computer graphics algorithms, such as fractals and the Mandelbrot set, use recursion to
generate complex patterns.