School of Computer Science and Engineering
Data Structures using JAVA [R1UC303B]
Module-III: Recursion
Dr. A K Yadav
School of Computer Science and Engineering
Plat No 2, Sector 17A, Yamuna Expressway
Greater Noida, Uttar Pradesh - 203201
November 24, 2024
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 1/24
School of Computer Science and Engineering
Contents
Recursion 3
Direct Recursion 6
Indirect Recursion 14
Removal of recursion 15
Iteration and recursion with examples 17
Trade-off between iteration and recursion 23
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 2/24
School of Computer Science and Engineering
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.
Need of Recursion:
I 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.
I It has certain advantages over the iteration technique which
will be discussed later.
I 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.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 3/24
School of Computer Science and Engineering
Properties of Recursion:
I Performing the same operations multiple times with different
inputs.
I In every step, we try smaller inputs to make the problem
smaller.
I Base condition is needed to stop the recursion otherwise
infinite loop will occur.
Algorithmic Steps:
The algorithmic steps for implementing recursion in a function are
as follows:
1 - Define a base case: Identify the simplest case for which the
solution is known or trivial. This is the stopping condition for
the recursion, as it prevents the function from infinitely calling
itself.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 4/24
School of Computer Science and Engineering
2 - Define a recursive case: Define the problem in terms of
smaller subproblems. Break the problem down into smaller
versions of itself, and call the function recursively to solve
each subproblem.
3 - Ensure the recursion terminates: Make sure that the
recursive function eventually reaches the base case, and does
not enter an infinite loop.
4 - Combine the solutions: Combine the solutions of the
subproblems to solve the original problem.
Types of Recursions:
- 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.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 5/24
School of Computer Science and Engineering
Direct Recursion
When a function calls itself from within itself is called direct
recursion. These can be further categorized into four types:
I 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.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 6/24
School of Computer Science and Engineering
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 7/24
School of Computer Science and Engineering
I Head Recursion: If a recursive function calling itself and that
recursive call is the first statement in the function then it’s
known as Head Recursion.
- There’s no statement, no operation before the call.
- The function doesn’t have to process or perform any
operation at the time of calling and all operations are done at
returning time.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 8/24
School of Computer Science and Engineering
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 9/24
School of Computer Science and Engineering
I Tree Recursion: If a recursive function calling itself for one
time then it’s known as Linear Recursion. Otherwise if a
recursive function calling itself for more than one time then
it’s known as Tree Recursion.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 10/24
School of Computer Science and Engineering
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 11/24
School of Computer Science and Engineering
I Nested Recursion: In this recursion, a recursive function will
pass the parameter as a recursive call. That means recursion
inside recursion.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 12/24
School of Computer Science and Engineering
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 13/24
School of Computer Science and Engineering
Indirect Recursion
In this recursion, there may be more than one functions and they
are calling one another in a circular manner.
In 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.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 14/24
School of Computer Science and Engineering
Removal of recursion
By replacing the selection structure with a loop, recursion can be
eliminated. A data structure is required in addition to the loop if
some data needs to be kept for processing beyond the end of the
recursive step. A simple string, an array, or a stack are examples of
data structures.
There are a few ways to remove recursion from code, including:
I Iteration: Wrap your algorithm in a loop, pushing and popping
a custom call stack at the start and end of each iteration.
I Macro expansion: This technique can eliminate recursion, but
the depth of recursion is limited by the number of macro
invocations.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 15/24
School of Computer Science and Engineering
I Refactoring: In Python, you can refactor the code using a
series of small, careful refactorings to remove a single
recursion.
I Stack: You can use a stack to store a representation of the
operations that need to be performed.
I Generalization: Generalize the function definition.
I Computation traces: Study the computation traces of the
function.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 16/24
School of Computer Science and Engineering
Iteration and recursion with examples
I Linear Search
Figure: Linear Search Iterative
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 17/24
School of Computer Science and Engineering
Figure: Linear Search Recursive
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 18/24
School of Computer Science and Engineering
I Fibonacci Numbers
Figure: Fibonacci Numbers Iterative
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 19/24
School of Computer Science and Engineering
Figure: Fibonacci Numbers Recursive
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 20/24
School of Computer Science and Engineering
Figure: Fibonacci Function Call
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 21/24
School of Computer Science and Engineering
I Tower of Hanoi
Figure: Tower of Hanoi
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 22/24
School of Computer Science and Engineering
Trade-off between iteration and recursion
The trade-offs between iteration and recursion in programming
include:
I Speed: Iteration is generally faster than recursion.
I Memory: Recursion requires more memory than iteration.
I Code complexity: Recursion can lead to simpler, more
readable code, while iteration can result in more complex
code.
I Time complexity: Recursion has higher time complexity than
iteration.
I Approach: Recursion follows a divide and conquer approach,
while iteration follows a sequential execution approach.
I Suitability: Recursion is better for tasks that can be described
naturally in a recursive way, while iteration is better for loops.
I Optimization: It can be difficult to optimize recursive code.
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 23/24
School of Computer Science and Engineering
Thank you
Please send your feedback or any queries to
ashokyadav@[Link]
Module-III: Recursion Dr. A K Yadav Data Structures using JAVA 24/24