Chapter 2
Recursion
Objectives
Upon completion you will be able to:
• Explain the difference between iteration and recursion
• Design a recursive algorithm
• Determine when an recursion is an appropriate solution
• Write simple recursive functions
Data Structures: A Pseudocode Approach with C 1
2-1 Factorial - A Case Study
We begin the discussion of recursion with a case
study and use it to define the concept.
This section also presents an iterative and a
recursive solution to the factorial algorithm.
• Recursive Defined
• Recursive Solution
Data Structures: A Pseudocode Approach with C 2
Data Structures: A Pseudocode Approach with C 3
Data Structures: A Pseudocode Approach with C 4
Data Structures: A Pseudocode Approach with C 5
Data Structures: A Pseudocode Approach with C 6
Data Structures: A Pseudocode Approach with C 7
Data Structures: A Pseudocode Approach with C 8
2-2 Designing Recursive Algorithms
In this section we present an analytical
approach to designing recursive algorithms.
We also discuss algorithm designs that are not
well suited to recursion.
• The Design Methodology
• Limitation of Recusion
• Design Implemenation
Data Structures: A Pseudocode Approach with C 9
Data Structures: A Pseudocode Approach with C 10
Data Structures: A Pseudocode Approach with C 11
2-3 Recursive Examples
Four recursive programs are developed and
analyzed. Only one, the Towers of Hanoi, turns
out to be a good application for recursion.
• Greatest Common Divisor
• Fiboncci Numbers
• Prefix to Postfix Conversion
• The Towers of Honoi
Data Structures: A Pseudocode Approach with C 12
Slide 05
Data Structures: A Pseudocode Approach with C 13
Data Structures: A Pseudocode Approach with C 14
Data Structures: A Pseudocode Approach with C 15
Data Structures: A Pseudocode Approach with C 16
Data Structures: A Pseudocode Approach with C 17
Data Structures: A Pseudocode Approach with C 18
(Continued)
Data Structures: A Pseudocode Approach with C 19
Data Structures: A Pseudocode Approach with C 20
Data Structures: A Pseudocode Approach with C 21
Data Structures: A Pseudocode Approach with C 22
Data Structures: A Pseudocode Approach with C 23
Data Structures: A Pseudocode Approach with C 24
Data Structures: A Pseudocode Approach with C 25
Data Structures: A Pseudocode Approach with C 26
Data Structures: A Pseudocode Approach with C 27
Data Structures: A Pseudocode Approach with C 28
Data Structures: A Pseudocode Approach with C 29
Data Structures: A Pseudocode Approach with C 30
Data Structures: A Pseudocode Approach with C 31
Data Structures: A Pseudocode Approach with C 32
Data Structures: A Pseudocode Approach with C 33
Data Structures: A Pseudocode Approach with C 34
(Continued)
Data Structures: A Pseudocode Approach with C 35
Data Structures: A Pseudocode Approach with C 36
Data Structures: A Pseudocode Approach with C 37
Data Structures: A Pseudocode Approach with C 38
Data Structures: A Pseudocode Approach with C 39
Data Structures: A Pseudocode Approach with C 40
Data Structures: A Pseudocode Approach with C 41
Data Structures: A Pseudocode Approach with C 42
Data Structures: A Pseudocode Approach with C 43
Data Structures: A Pseudocode Approach with C 44
