[go: up one dir, main page]
Scribd
Upload
28 views18 pages

7 Recursion

Uploaded by

22071186
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
28 views18 pages

7 Recursion

Uploaded by

22071186
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/ 18

DATA STRUCTURES AND ALGORITHMS

Chapter 7: Recursion

1
Main contents

• Recursive definition

• Recursion Essentials

• Recursive program/algorithm

• Advantages and disadvantages of recursion

• Anatomy of a recursive call

• Recursion application

2
Introduction
• Recursion is a repetitive process in which a function calls
itself either directly or indirectly.
• Recursion is a technique that allows us to break down a
problem into one or more sub-problems that are similar
in form to the original problem
• In recursion, each time when the recursive function is
called, the current state including all the local variables,
formal parameters, and return address are pushed into
the stack.

3
Recursive definition
A recursive definition or inductive definition is
one that defines something in terms of itself
(that is, recursively). For it to work, the definition
in any given case must be well-founded,
avoiding an infinite regress.
Example: Define the set of natural numbers
1. 0  N
2. if n  N , then (n  1)  N
3. there are no other objects in the set N
4/25
Recursion Essentials
A recursive definition consists of at least 2 parts:
1) A base criteria (or base case) that does not contain a
reference to its own type.
2) An inductive case that does contain a reference to its
own type.
When the recursion does not terminate, we have
an infinite regress. Infinite regress often occurs
when:
i) A base criterion is omitted or
ii) When a base criterion is never reached.
5/25
Recursion Essentials
Example: Find factorial of a number using recursion

6/25
Recursive program/algorithm
Example: Find factorial of a number using recursion

base case
(no recursion call)

inductive case
(recursion call)

7/25
Recursive program/algorithm
Example: Write the program to define the nth number
in Fibonacci sequence:

8/25
Other examples of recursion
- Find the greatest common divisor (GCD) or
highest common factor (HCF) of two non-
negative, not- both-zero integers.
- Tower of Hanoi
- Non-Attacking Queens

9
Types of Recursion
- Whether the function calls itself or not (direct or
indirect/mutual recursion).
- How many internal recursive calls are made there within
the body (linear, binary, and non-linear recursion)?
- Whether there are pending operations or not at each
recursive call (tail or non-tail recursion).
- Recursion is mainly two types depending on whether a
function calls itself or not.
+ Direct Recursion
+ Indirect Recursion or Mutual Recursion

10
Advantages of Recursion
 Recursion functions can be written easily.

 Some complex problems can be easily understood


and implements using recursion (Tower of Hanoi,
Non-attacking Queens, …).

 The recursive definitions can be translated into


recursive function easily.

11/25
Disadvantages of Recursion
 Recursion consumes more storage space
 The computer may run out of memory if base
criteria are not checked.
 Recursion is not efficient in terms of speed and
execution time,

12/25
Differences between iteration and recursion

13/25
Differences between iteration and recursion

Example: Write the iteration (non-recursion) program


to find the nth number in Fibonacci sequence :

14/25
Anatomy of a recursive call

Example: Recursion tree of Fib(5) – find the 5th of


Fibonacci sequence

15/25
Anatomy of a recursive call

Example: Analyze a function call fact(4): find the


factorial of 4;

16/25
17
Summary

- Recursion is a repetitive process in which a function


calls itself either directly or indirectly.
- Infinite recursion occurs in a program when base
criteria are omitted or base criteria are never
reached, it results in a stack overflow.
- A recursive function is said to be tail recursive if there
are no pending operations to be performed on return
from a recursive call.
- Recursion consumes more storage space and
execution time

18

You might also like