PPT: Recursion | Programming and Data Structures - Computer Science Engineering (CSE) PDF Download

 Page 1


R e c u r s i o n
Page 2


R e c u r s i o n
What is Recursion?
Recursion is the process in which a function calls itself directly or indirectly. The corresponding 
function is called a recursive function. Using recursive algorithms, certain problems can be 
solved quite elegantly.
Self-Referential
A function that calls itself 
within its own definition, 
creating a loop-like 
structure that continues 
until a base condition is 
met.
Problem Solving
Breaks complex problems 
into smaller, more 
manageable subproblems 
of the same type.
Common Applications
Towers of Hanoi, Tree 
Traversals 
(Inorder/Preorder/Postord
er), and Depth-First 
Search of Graphs.
Page 3


R e c u r s i o n
What is Recursion?
Recursion is the process in which a function calls itself directly or indirectly. The corresponding 
function is called a recursive function. Using recursive algorithms, certain problems can be 
solved quite elegantly.
Self-Referential
A function that calls itself 
within its own definition, 
creating a loop-like 
structure that continues 
until a base condition is 
met.
Problem Solving
Breaks complex problems 
into smaller, more 
manageable subproblems 
of the same type.
Common Applications
Towers of Hanoi, Tree 
Traversals 
(Inorder/Preorder/Postord
er), and Depth-First 
Search of Graphs.
Mathematical Interpretation
Let's consider the problem of determining the sum of first n natural numbers. There are multiple 
approaches to solve this:
Iterative Approach
Simply adding numbers one by one:
f(n) = 1 + 2 + 3 + ... + n
Recursive Approach
Using self-reference to solve:
f(n) = 1 if n=1
f(n) = n + f(n-1) if n>1
The key difference is that in the recursive approach, the function "f()" calls itself inside its definition. 
This powerful technique allows programmers to code some problems in a much easier and more 
efficient way.
Page 4


R e c u r s i o n
What is Recursion?
Recursion is the process in which a function calls itself directly or indirectly. The corresponding 
function is called a recursive function. Using recursive algorithms, certain problems can be 
solved quite elegantly.
Self-Referential
A function that calls itself 
within its own definition, 
creating a loop-like 
structure that continues 
until a base condition is 
met.
Problem Solving
Breaks complex problems 
into smaller, more 
manageable subproblems 
of the same type.
Common Applications
Towers of Hanoi, Tree 
Traversals 
(Inorder/Preorder/Postord
er), and Depth-First 
Search of Graphs.
Mathematical Interpretation
Let's consider the problem of determining the sum of first n natural numbers. There are multiple 
approaches to solve this:
Iterative Approach
Simply adding numbers one by one:
f(n) = 1 + 2 + 3 + ... + n
Recursive Approach
Using self-reference to solve:
f(n) = 1 if n=1
f(n) = n + f(n-1) if n>1
The key difference is that in the recursive approach, the function "f()" calls itself inside its definition. 
This powerful technique allows programmers to code some problems in a much easier and more 
efficient way.
Base Condition in Recursion
In recursive programming, a base condition is essential to prevent infinite recursion. It provides the solution f or the 
simplest case and stops the recursive calls.
Define the Base Case
Identify the simplest version of the problem that can be sol ved directly.
Implement the Base Condition
Add a conditional statement that returns a value when the base case is reached.
Recursive Case
Express larger problems in terms of smaller ones until the base case is reached.
For example, in a factorial function, the base case is when n f 1, which returns 1. For larger values, the func tion calls itself 
with a smaller input until it reaches the base case.
Page 5


R e c u r s i o n
What is Recursion?
Recursion is the process in which a function calls itself directly or indirectly. The corresponding 
function is called a recursive function. Using recursive algorithms, certain problems can be 
solved quite elegantly.
Self-Referential
A function that calls itself 
within its own definition, 
creating a loop-like 
structure that continues 
until a base condition is 
met.
Problem Solving
Breaks complex problems 
into smaller, more 
manageable subproblems 
of the same type.
Common Applications
Towers of Hanoi, Tree 
Traversals 
(Inorder/Preorder/Postord
er), and Depth-First 
Search of Graphs.
Mathematical Interpretation
Let's consider the problem of determining the sum of first n natural numbers. There are multiple 
approaches to solve this:
Iterative Approach
Simply adding numbers one by one:
f(n) = 1 + 2 + 3 + ... + n
Recursive Approach
Using self-reference to solve:
f(n) = 1 if n=1
f(n) = n + f(n-1) if n>1
The key difference is that in the recursive approach, the function "f()" calls itself inside its definition. 
This powerful technique allows programmers to code some problems in a much easier and more 
efficient way.
Base Condition in Recursion
In recursive programming, a base condition is essential to prevent infinite recursion. It provides the solution f or the 
simplest case and stops the recursive calls.
Define the Base Case
Identify the simplest version of the problem that can be sol ved directly.
Implement the Base Condition
Add a conditional statement that returns a value when the base case is reached.
Recursive Case
Express larger problems in terms of smaller ones until the base case is reached.
For example, in a factorial function, the base case is when n f 1, which returns 1. For larger values, the func tion calls itself 
with a smaller input until it reaches the base case.
Solving Problems with Recursion
The key to solving problems recursively is to represent them in terms of smaller versions of themselves, 
with clearly defined base conditions to stop the recursion.
Identify the Base Case
Define the simplest version of the problem that can be solved directly without further recursion.
Define the Recursive Case
Express the solution in terms of smaller subproblems of the same type.
Ensure Progress Toward Base Case
Each recursive call must move closer to the base case to ensure termination.
For example, with factorial: we compute factorial(n) by knowing factorial(n-1). The base case is n = 0, which 
returns 1. Each recursive call decreases n by 1, ensuring we eventually reach the base case.