Recursion, Linked Lists, and ADTs
Overview
• Recursion
• Singly-Linked Lists • Abstract Data Types
References
• Bruno R. Preiss: Data Structures and Algorithms with Object-Oriented Design Patterns in C++. John Wiley & Sons, Inc. (1999)
• Richard F. Gilberg and Behrouz A. Forouzan: Data Structures – A Pseudocode Approach with C. 2nd Edition. Thomson (2005)
• Russ Miller and Laurence Boxer: Algorithms Sequential & Parallel. 2nd Edition. Charles River Media Inc. (2005)
• Stanley B. Lippman, Josée Lajoie, and Barbara E. Moo: C++ Primer. 4th Edition. Addison-Wesley (2006)
192
© Dr Markus Lumpe, 2021
Recursion
• If a procedure contains within its body calls to itself, then this procedure is said to be recursively defined.
•This approach of program specification is called recursion and is found not only in programming.
• If we the define a procedure recursively, then there must exist at least one sub-problem that can be solved directly, that is without calling the procedure again.
• A recursively defined procedure must always contain a directly solvable sub-problem. Otherwise, this procedure does not terminate.
193
© Dr Markus Lumpe, 2021
Problem-Solving with Recursion
•Recursion is an important problem-solving technique in which a given problem is reduced to smaller instances of the same problem.
• The general structure of a recursive definition is
X = … X …
Right-hand side
Left-hand side
194
© Dr Markus Lumpe, 2021
Impossible Recursive Structures
http://www.mcescher.com/
Fair use of material subject to copyright: Low resolution images for educational presentation on recursion.
195
© Dr Markus Lumpe, 2021
Impossible Structures in C++:
#include “ClassB.h”
class ClassA
{
use ClassB
};
#include “ClassA.h”
class ClassB
{
use ClassA
};
196
© Dr Markus Lumpe, 2021
Forward Declaration
• Unlike in Java or C#, we cannot define mutual recursive classes in C++.
• We must resolve the dependency manually and use forward declarations in specifications.
• In the implementations, we must include all specifications, so that the compiler can resolve the dependencies.
class ClassB;
class ClassA
{
use ClassB
};
class ClassA;
class ClassB
{
use ClassA
};
#include “ClassA.h” #include “ClassB.h”
implement ClassA implement ClassB
197
© Dr Markus Lumpe, 2021
Basic Recursive Problems
198
© Dr Markus Lumpe, 2021
Fibonacci
• The Fibonacci numbers are the following sequence of numbers: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …
• In mathematical terms, the sequence F(n) of Fibonacci numbers is defined recursively as follows:
F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)
199
© Dr Markus Lumpe, 2021
Recursive Problem-Solving: Factorials
• The factorial for positive integers is
n! = n * (n – 1) * … * 1
• The recursive definition:
{1 if n = 0 n* (n-1)! if n > 0
n! =
200
© Dr Markus Lumpe, 2021
Calculating Factorials
• The recursive definition tells us exactly how to calculate a factorial:
4! =4*3! =4*(3 =4*(3 =4*(3 =4*(3 = 4 * (3 = 4 * (3
=4*6 = 24
* 2!)
*(2 * 1!))
*(2 * (1 * 0!))) *(2 * (1 * 1))) * (2 * 1))
* 2)
Recursive step: n=4 Recursive step: n=3 Recursive step: n=2 Recursive step: n=1 Stop condition: n=0
201
© Dr Markus Lumpe, 2021
Recursive Factorial
202
© Dr Markus Lumpe, 2021
Tail-Recursion
• A function is called tail-recursive if it ends in a recursive call that does not build-up any deferred operations.
gcd( 1246, 234 ): ➥ gcd( 234, 76 ) ➥ gcd( 76, 6 ) ➥ gcd( 6, 4 )
➥ gcd( 4, 2 ) ➥ gcd( 2, 0 ) ➥2
203
© Dr Markus Lumpe, 2021
Towers of Hanoi
• Problem:
Move disks from a start peg to a target peg using a middle peg.
• Challenge:
All disks have a unique size and at no time must a bigger disk be placed on top of a smaller one.
•
•
204
© Dr Markus Lumpe, 2021
Towers of Hanoi: Configuration
Start:
Start
Middle
Target
Finish:
Start
Middle 205
Target
© Dr Markus Lumpe, 2021
A Recursive Solution
1. Move n-1 disks from Start to Middle:
Start Middle
Target
2. Move 1 disk from Start to Target:
Target
Start Middle
3. Move n-1 disks from Middle to Target:
Start Middle
Target
© Dr Markus Lumpe, 2021
A Recursive Solution: Intermediate
Start
Start Start Start
Middle
Middle
Middle Middle
Target Target
Target
Target
© Dr Markus Lumpe, 2021
207
The Recursive Procedure
208
© Dr Markus Lumpe, 2021
Bézier Curves
• Bézier curves are created by linear interpolation between points. The parameter t ∈ [0,1] controls how far we move p1 between two points. For example, any point on the line between p0 and p1 can be denoted by (1-t)p0 + tp1, that is,
(1 − t)p0 + tp1
(1−t)2p0 +2t(1−t)p1 +t2p2
(1 − t)p1 + tp2
the “mid point” of p0 and p1 relative to parameter t.
• Repeating this process (for all points and line segments)
gives us a point on a Bézier curve.
• The factors for each points are the components of the corresponding Bernstein Basis Polynomial. The recursive “mid point” formula below, however, yields a much more
p0
Pij =
( (1−t)Pj−1+tPj−1 if j>0 i i−1
Pi otherwise 209
p2 stable operation compared to computing directly Bernstein Basis Polynomial terms.
© Dr Markus Lumpe, 2021
Recursion is a prerequisite for linked lists!
210
© Dr Markus Lumpe, 2021