Scribd
Upload
12 views10 pages

Introduction to Recursion Concepts

This lecture introduces recursion, defining it as a function that calls itself to solve problems. It contrasts recursion with iteration, highlighting their differences in termination conditions and structure. The lecture also explains the components of recursive functions, provides an example using factorial calculation, and discusses recursion trees.

Uploaded by

Muhammad umar Jamali
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views10 pages

Introduction to Recursion Concepts

This lecture introduces recursion, defining it as a function that calls itself to solve problems. It contrasts recursion with iteration, highlighting their differences in termination conditions and structure. The lecture also explains the components of recursive functions, provides an example using factorial calculation, and discusses recursion trees.

Uploaded by

Muhammad umar Jamali
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

LECTURE # 03

INTRODUCTION TO
RECURSION

Instructor:
[Link]-e-Shawar Agha
ROAD MAP
 Introduction to recursion
 Difference between iteration and
recursion
 Example of recursion
 Recursion Tree
TYPES OF ALGORITHM
RECURSION
 Any function which calls itself is called recursion.

OR

 A problem solving or programming technique in


which a method(function) can call itself in order
to solve the problem.
DIFFERENCE BETWEEN ITERATION AND
RECURSION

 Iteration uses a repetition statement and


recursion uses a selection statement.

 Iteration terminates when the loop continuation


condition fails. Recursion terminates when a base
case is reached.
PARTS OF RECURSIVE FUNCTION
 There are two main parts to recursive functions:
 General/Recursive/Inductive case: The case
for which the solution is expressed in terms of a
smaller version of itself function)
 Rules are given that allow for the construction of
new objects out of basic elements or the objects
that have already been constructed.
 There should be at least one general case
otherwise no recursion.
 Anchor/Ground/Base case: The case for which
the solution can be stated non-recursively. Here,
a solid solution is found.
EXAMPLE
 Let's take an example of recursion using the
factorial for a positive integer n factorial can be
represented by:

int factorial(int n) { anchor / base case


if (n = = 0)
return 1;
else
return n * factorial (n – 1); Inductive Case
}
WORKING OF FACTORIAL

4!=4 * (3!)
=4 * (3 * (2!))
=4 * (3 * (2 * (1!)))
=4 * (3 * (2 * (1 * (0!))))
=4 * (3 * (2 * (1 * (1))))
RECURSION TREE
SUMMARY

 Recursion and its example

 Recursion Tree

You might also like