[go: up one dir, main page]
Scribd
Upload
11 views11 pages

Lecture 6

The document discusses recursion in data structures, explaining its definition, properties, and applications. It highlights the importance of base criteria and progressive approaches to prevent infinite recursion and lists various applications such as the Fibonacci series, factorial calculation, and sorting algorithms. Additionally, it includes examples and a class assignment related to recursive functions.

Uploaded by

Khalid Ahmad Ghiasi
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
11 views11 pages

Lecture 6

The document discusses recursion in data structures, explaining its definition, properties, and applications. It highlights the importance of base criteria and progressive approaches to prevent infinite recursion and lists various applications such as the Fibonacci series, factorial calculation, and sorting algorithms. Additionally, it includes examples and a class assignment related to recursive functions.

Uploaded by

Khalid Ahmad Ghiasi
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
You are on page 1/ 11

Data

Structures
Recursion in dataStructure

Lecture : 6
Lecturer: Khalid Ahmad
“Mubariz”
Agenda
v Introduction to
Recursion
v Application of
recursion
v Backtracking
v Examples
Recursion

• Some computer programming languages


allow a module or function to call itself.
This technique is known as recursion. In
recursion, a function α either calls itself
directly or calls a function β that in turn
calls the original function α. The
function α is called recursive function.
• A recursive function can go infinite
like a loop. To avoid infinite
running of recursive function,
there are two properties that a
recursive function must have
• Base criteria − There must be at
least one base criteria or
condition, such that, when this
condition is met the function stops
calling itself recursively.
• Progressive approach − The
recursive calls should progress in
such a way that each time a
recursive call is made it comes
closer to the base criteria
Properties
Implementation
• Many programming languages implement recursion by means
of stacks. Generally, whenever a function (caller) calls
another function (callee) or itself as callee, the caller function
transfers execution control to the callee. This transfer
process may also involve some data to be passed from the
caller to the callee.
Application of Recursion
•
• Divide and conquer
• Fibonacci Series
Algorithm
• Factorial of a numbered • Tower of Hanoi
• Merge sort, Quick sort • Backtracking Algorithm
• Binary search
• Tree traversal
• Graph traversal
Example

• Finding factorial of a number using recursion


Fibonacci Series
• Fibonacci series generates the subsequent number by adding two
previous numbers.
• Fibonacci series starts from two numbers − F0 & F1 .
• The initial values of F0 & F1 can be taken 0, 1 or 1, 1 respectively.
• Fibonacci series satisfies the following conditions −
• Fn = Fn-1 + Fn-
• Hence, a Fibonacci series can look like this −
• F8 = 0 1 1 2 3 5 8 13
• or, this −
• F8 = 1 1 2 3 5 8 13 21
Example
• Finding Fibonacci series
Class work.
• Write a recursive Function to
calculate the Greatest
Common Divisor of two
number.
Thank you
Khalid Ahmad “Mubariz”
khalidahmadghiasi@gmail.com

You might also like