Lecture 9:
Recursion
CS 136: Spring 2024
Katie Keith
📣 Announcements
5 minute bathroom break
Quiz 1: Last 25 minutes of class
🎯 Today’s Learning Objectives
📚Readings
JavaDocs for ArrayList
Some human developers wrote this many decades ago! We will all take the role of those original developers!
We’ll use the interface we just implemented, OurListInterface
OurArrayList.java
💻
ADT vs. Data Structures
Abstract Data Type (ADT) | Data Structure |
Defines a particular set of operations that can be performed on data, without describing how they are implemented. | The ADT implementation in a programming language (in CS 136: Java!) |
Example: A List is a linear ADT in which elements are arranged in a sequential order. Operations: Insertion, Deletion, Access, Traversal etc. | Multiple data structures can implement the same ADT. Example: (1) A list implemented with arrays (ArrayLists) (2) A list implemented with singly-linked lists |
Theoretical. The “what.” | Concrete. The “how.” |
In Java: Interfaces | In Java: Classes that implement interfaces |
Why is recursion important to CS 136?
Looking ahead, we will use recursion throughout CS 136.
Recursion
Recursion is a general problem solving strategy that we use when:
Figure credit: Wikipedia
Task: Find the greatest common divisor
Recall, the greatest common divisor (gcd) of two positive integers is the largest integer that divides evenly into both of them
Example:
gcd(20, 16) = 4
Applications to Cryptography: The GCD is used to ensure that certain key components are coprime (i.e., their GCD is 1), which is essential for the security and functionality of the encryption process.
Iterative approach
An iterative approach refers to repeating a set of operations until a certain condition is met. This is typically achieved using loops such as for or while.
public static int iterativeGcd(int p, int q){
int largest = 1; // 1 always divides everything
for(int i=2; i<=q; i++){
if (q % i == 0 && p % i == 0){
largest = i;
}
}
return largest;
}
This algorithm is correct but slow since we’re going through every single integer.
GCD: Euclid’s algorithm
Key insight: When p > q, the gcd(p,q) is the same as the gcd(q, p % q).
Preview: Take MATH 200: Discrete Math to prove why this works!
Preview: Next week we’ll show this is more efficient than the iterative algorithm (previous slide)
Example:
gcd(1071, 462)=?
Example from Wikipedia
Answer!
GCD.java
💻
Elements of a recursive method
public static int recursiveGcd(int p, int q){
if(q == 0){
return p;
}
else{
return recursiveGcd(q, p % q);
}
}
Base case: Returns a value without making any subsequent recursive calls.
Recursive step: It relates the value of the function at one (or more) input values to the value of the function at one (or more) other input values
Calling the name of the function
Modifying the inputs
Manually tracing recursion calls and returns
Board work
public static int gcd(int p, int q){
if(q == 0){
return p;
}
else{
return gcd(q, p % q);
}
}
We simplified the method name for ease of tracing
Review: Harmonic numbers from Lecture 3
The nth harmonic number is the sum of the reciprocals of the first n natural numbers
public static double harmonic(int n) {
double sum = 0.0;
for (int i = 1; i <= n; i++) {
sum += 1.0 / i;
}
return sum;
}
Our iterative solution from Lecture 3
We make the following attempts to write a recursive version of calculating harmonic numbers.
These attempts fail, but for different reasons. Make some guesses as to what these reasons could be.
// Version A
public static double harmonic(int n){
return harmonic(n-1) + 1.0/n;
}
// Version B
public static double harmonic(int n){
if(n==1){
return 1.0;
}
return harmonic(n) + 1.0/n;
}
💡Think-pair-share
5 minute bathroom break
Quiz 1: Last 25 minutes of class
✅
🎯 Today’s Learning Objectives