Kandahar University
Education Faculty
Computer Learning
Recursion
Lecturer: Mohammad Nabi “Hotak”
Semester: 7th
Subject: Data Structures II
Contents
➢ What is recursion?
➢ Need of Recursion
➢ Properties of Recursion
➢ Recursion vs Iteration
➢ Implementation
Mohammad Nabi Hotak 10/21/2024 2
Introduction to Recursion
INTRODUCTION TO RECURSION
Introduction
▪ 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.
Mohammad Nabi Hotak 10/21/2024 4
Need of Recursion
NEED OF RECURSION
Need of Recursion
▪ Recursion is a best 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.
▪ Formula: n!=n×(n−1)×(n−2)×⋯×1
▪ Example: 5!=5×4×3×2×1=120
Mohammad Nabi Hotak 10/21/2024 6
Properties of Recursion
PROPERTIES OF RECURSION
Properties and Base Case
• 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.
Mohammad Nabi Hotak 10/21/2024 8
Direction vs Indirect
Direction vs 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.
Mohammad Nabi Hotak 10/21/2024 9
Direction vs Indirect
Direction vs 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.
Mohammad Nabi Hotak 10/21/2024 10
Direction vs Indirect
Direction vs Indirect recursion
Mohammad Nabi Hotak 10/21/2024 11
Recursion vs Iterations
Recursion vs Iterations
Recursion vs Iterations
Mohammad Nabi Hotak 10/21/2024 13
IMPLEMENATION USING
JAVA / C#
IMPLEMENATION
Iterative Approach
Recursion Approach
Mohammad Nabi Hotak 10/21/2024 15
IMPLEMENATION
THE END
QUESTION?
Mohammad Nabi Hotak 10/21/2024 16