9 min read•Last Updated on June 18, 2024
Avanish Gupta
Milo Chang
Avanish Gupta
Milo Chang
Using recursion, we can make our searching and sorting algorithms from Unit 7 much more concise, and we will also have new searching and sorting algorithms that may be more efficient than our previous algorithms!
We already covered this iteratively in Topic 7.5. As a reminder, here is the iterative code:
public static int linearSearch(ArrayList<Integer> array, int n) {
for (int i = 0; i < array.size(); i++) {
if (array.get(i) == n) {
return i;
}
}
return -1;
}
Here is the recursive version:
public static int recursiveLinearSearch(ArrayList<Integer> array, int n, int startingIndex) {
if (array.get(startingIndex) == n) {
return startingIndex; // base case #1: element found
} else if (startingIndex == array.size() - 1) {
return -1; //base case #2: element not found
} else {
//[recursive call](https://www.fiveableKeyTerm:Recursive_Call) to check next element
return recursiveLinearSearch(array, n, startingIndex + 1);
}
}
//To use this method:
recursiveLinearSearch(array, n, 0);
Binary search is the new search algorithm that we'll learn in this unit, and it is quicker than linear sort. However, the tradeoff for the speed is that the list has to be presorted. Binary search will not work if the data is not presorted.
Here is its implementation, along with how it works both iteratively and recursively:
/** Uses binary search on a sorted ArrayList
* 1. Looks at the middle of the list, which divides it into two sublists
* 2. The left sublist is less than the middle and the right is greater
* 3. Compare the value to be searched for to the middle value
* 4. If this value > middle, repeat 1-3 to the right sublist
* 5. If this value < middle, repeat 1-3 to the left sublist
* 6. If this value = middle, return the middle value
* 7. Return -1 if value not found
*/
public static int binarySearch(ArrayList<Integer> array, int n) {
int left = 0;
int right = array.size() - 1;
while (left <= right) { // left > right is "illegal"
int middle = (left + right) / 2; // get the middle index of sublist
if (n == array.get(middle)) { // item in middle of sublist
return middle;
} else if (n < array.get(middle)) { // item in left sublist
right = middle - 1;
} else if (n > array.get(middle)) { // item in right sublist, could just use else
left = middle + 1;
}
}
return -1; // item not in list
}
public static int recursiveBinarySearch(ArrayList<Integer> array, int n, int left, int right) {
int middle = (left + right) / 2; // get the middle index of sublist
if (left > right) { // base case #1: item not in list
return -1;
} else if (n == array.get(middle)) { // base case #2: item in middle of sublist
return middle;
} else if (n < array.get(middle)) { // recursive call #1: item in left sublist
return recursiveBinarySearch(array, n, left, middle - 1);
} else if (n > array.get(middle)) { // recursive call #2: item in right sublist, could just use else
return recursiveBinarySearch(array, n, middle + 1, right);
}
}
//To use this, call:
recursiveBinarySearch(array, n, 0, array.size() -1);
Here is a visualization of binary search:
We already covered this iteratively in Topic 7.6. As a reminder, here is the iterative code:
/** Uses insertion sort on an ArrayList
* 1. Assume the first element is already sorted
* 2. Select the second element
* 3. Insert it before the first element or keep it in place to make the first 2 elements sorted
* 4. Select the third element and insert it so that the first 3 elements are sorted
* 5. Repeat until all elements are sorted.
*/
public static ArrayList<Integer> insertionSort(ArrayList<Integer> array) {
for (int i = 1; i < array.length(); i++) {
int currentElement = array.get(i);
int currentIndex = i;
for (int j = i; j > 0 ; j--) {
if (currentElement < array.get(j - 1)) {
// shifting the item left until properly placed by swapping consecutive items
int itemToRight = array.get(j - 1);
array.set(j - 1, currentElement);
array.set(j, itemToRight);
}
}
}
return array;
}
Here is the recursive version:
public static ArrayList<Integer> recursiveInsertionSort(ArrayList<Integer> array, int index) {
if (index == array.size()) { // base case: end of list reached, list sorted
return array;
} else {
int currentItem = array.get(index)
for (int i = index; i > 0; i--) { // shifting item to the left until sorted
if (currentItem < array.get(i - 1)) {
int itemToRight = array.get(i - 1);
array.set(i - 1, currentItem);
array.set(i, itemToRight);
}
}
return recursiveInsertionSort(array, index + 1); // recursive call to sort the next item
}
}
//To use this method:
recursiveInsertionSort(array, 0);
We already covered this iteratively in Topic 7.6. As a reminder, here is the iterative code:
/** Uses [selection sort](https://www.fiveableKeyTerm:Selection_Sort) on an ArrayList
* 1. Originally the ArrayList is unsorted
* 2. We select the smallest number and swap it with the first element
* 3. Now the sorted subarray is the first item and the rest of the array is unsorted
* 4. Select the smallest of the unsorted numbers (the second smallest overall) and
* swap it with the second element
* 5. Now the first two elements are sorted and the rest are unsorted
* 6. Repeat until the rest of the elements are sorted
*/
public static ArrayList<Integer> selectionSort(ArrayList<Integer> array) {
for (int i = 0; i < array.size() - 1; i++) {
// traverse to the second to last item, the last item is automatically the largest
int smallestIndex = i;
int smallestElement = array.get(i);
for (int j = i + 1; i < array.size(); j++) {
//traverse through the rest of the array,
//looking for the smallest remaining item (less than smallestElement)
if (array.get(j) < smallestElement) {
smallestIndex = j;
smallestElement = array.get(j);
}
}
if (smallestIndex > i) {
// swap the elements of i and j if the element of i isn't already the smallest
int originalItem = array.get(i);
array.set(i, smallestElement);
array.set(smallestIndex, originalItem);
}
}
return array;
}
Here is the recursive version:
public static ArrayList<Integer> recursiveSelectionSort(ArrayList<Integer> array, int index) {
if (index == array.size()) {
return array;
} else {
int smallestIndex = index;
int smallestElement = array.get(index);
for (int i = index + 1; i < array.size(); i++) {
if (array.get(i) < smallestElement) {
smallestIndex = i;
smallestElement = array.get(i);
}
}
if (smallestIndex > index) {
int originalItem = array.get(index);
array.set(index, smallestElement);
array.set(smallestIndex, originalItem);
}
return recursiveSelectionSort(array, index + 1);
}
}
//To use this method:
recursiveInsertionSort(array, 0);
Merge sort is the new sorting algorithm learned in this unit, and it is quicker than insertion and selection sort. However, the tradeoff for the speed is that the algorithm requires more memory.
Here is its implementation, along with how it works both iteratively and recursively:
/** Performs Merge sort (each version requires 2 methods, one specific to each version to split the lists and one common method to merge the sublists)
* 1. Split the list in half repeatedly (2 sublists, 4 sublists, 8, 16, ...) until each sublist has one item
2. Sort and Merge consecutive items until we get sorted sublists of length 2
3. Sort and Merge consecutive sublists of 2 to get sorted sublists of length 4
4. Repeat until the list is fully merged and sorted
*/
// ITERATIVE SPLITTING FUNCTION
// void bc the method adjusts the array itself, so you can call the array in an
// outside method
public static void mergeSort(ArrayList<Integer> array) {
// determine the size of the sublists to be merged
for (int currentSublistSize = 1; currentSublistSize < array.size();
currentSublistSize *= 2) {
// merge sublists of the current size
for (int startOfSubarray = 0; startOfSubarray < array.size() - 1;
startOfSubarray += 2 * currentSublistSize) {
// determine the end indices of the subarrays to be merged
int middle=Math.min(startOfSubarray + currentSublistSize - 1, array.size() - 1);
int endOfSubarray = Math.min(startOfSubarray + 2 * currentSublistSize - 1,
array.size() - 1);
merge(array, startOfSubarray, middle, endOfSubarray);
}
}
}
// RECURSIVE SPLITTING FUNCTION
public static void recursiveMergeSort(ArrayList<Integer> array, int left, int right) { // merge sorts a sublist from starting index left to ending index right
if (left < right) {
// if the sublist has more than 1 item
int middle = (left + right) / 2;
// split the sublist in half and mergeSort the halves
recursiveMergeSort(array, left, middle);
recursiveMergeSort(array, middle + 1, right);
merge(array, left, middle, right);
}
}
// MERGING FUNCTION
public static void merge(ArrayList<Integer> array, int left, int middle, int right) {
int leftLength = middle - left + 1;
int rightLength = right - middle;
// create 2 temporary ArrayLists for the left and right halves
int[] leftTemporary = new int[leftLength];
int[] rightTemporary = new int[rightLength];
for (int i = 0; i < leftLength; i++) {
// copy data into temp lists
leftTemporary[i] = array.get(left + i);
}
for (int i = 0; i < rightLength; i++) {
// copy data into temp lists
rightTemporary[i] = array.get(middle + 1 + i);
}
int i = 0;
int j = 0;
int k = left;
// start sorting the merged section of the array by combining the sublists
while (i < leftLength && j < rightLength) {
if (leftTemporary[i] <= rightTemporary[j]) {
array.set(k, leftTemporary[i]);
i++;
} else {
array.set(k, rightTemporary[j]);
j++;
}
k++;
}
while(i < leftLength) {
// copy remaining elements of left and right if sublists of different size
array.set(k, leftTemporary[i]);
i++;
k++;
}
while(j < rightLength) {
// copy remaining elements of left and right if sublists of different size
array.set(k, rightTemporary[j]);
j++;
k++;
}
}
Here is a visual look at merge sort:
If you've made it this far, congratulations, you've reached the end of AP Computer Science A! By now, you should be an expert on control structures — loops, recursion, and conditional statements, object orientated programming — abstraction/method writing, encapsulation/class writing, inheritance, and polymormism, and basic data structures — 1-D and 2-D arrays and ArrayLists!
If you're interested in further pursuing computer science, what comes next?
You will most likely take a set of two courses, one being a more mathematically orientated and the other being more programming orientated. The first is a discrete math class, which covers the theory of discrete sets, which consists of things that we can count on our fingers, like whole numbers, as opposed to continuous sets, which are uncountable, such as real numbers. In this class, you'll learn a lot of logic and proofs so that we can understand programs and algorithms more. You will also learn probability and state machines as well, which represent random algorithms and will help with machine learning and other fields where our methods are mostly consisting of random numbers with random outputs. Finally, you'll learn about graphs, which are a type of data structure that consists of different elements and connections between these elements.
On the other hand, the second Java course is a continuation of this course. You'll learn some advanced topics in inheritance and polymorphism with the introduction of the interface and the abstract class and also make better loops, recursion, and classes with what are known as invariants (which are the basis of the "Four Loopy Questions" in Unit 4). Then, you'll move onto more advanced data structures, including the following:
With AP CSA and these two courses, these set up the foundation for any computer science that you will do afterwards, like artificial intelligence and machine learning, algorithm analysis, programming language construction, graphics, web development, and so much more! The possibilities are endless! Moreover, there are many resources to learn these online as well and you don't need to go to a university to be a good programmer, but instead you can teach yourself and achieve great things!
If you have reached the end of this guide, thank you for sticking along on this journey through AP CSA. We as the Fiveable team have spent countless hours making and curating the best resources available for your use so that you can pass the AP exam and hopefully learn something new, fun, and insightful throughout this course that you can use later. We hope that you have found this information valuable and we wish you the best of luck on your AP exams and beyond!
Abstraction is the process of simplifying complex systems by breaking them down into smaller, more manageable parts. Method writing refers to defining behaviors or actions that an object can perform.
Term 1 of 36
Abstraction is the process of simplifying complex systems by breaking them down into smaller, more manageable parts. Method writing refers to defining behaviors or actions that an object can perform.
Term 1 of 36
Abstraction is the process of simplifying complex systems by breaking them down into smaller, more manageable parts. Method writing refers to defining behaviors or actions that an object can perform.
Term 1 of 36
Recursion is a programming technique where a function calls itself to solve a problem by breaking it down into smaller, similar subproblems.
Base Case: The base case in recursion is the condition that stops the recursive calls and provides an answer or solution directly without further recursion.
Recursive Call: A recursive call refers to when a function invokes itself during its execution to solve a smaller version of the original problem.
Stack Overflow: A stack overflow occurs when there are too many recursive function calls, causing the program's call stack memory to be exhausted.
Sorting algorithms are techniques used to arrange elements in a specific order (e.g., ascending or descending) within a collection of data.
Bubble Sort: A simple sorting algorithm that repeatedly compares adjacent elements and swaps them if they are in the wrong order.
Quick Sort: A divide-and-conquer sorting algorithm that selects a pivot element and partitions the array into two subarrays, then recursively sorts each subarray.
Selection Sort: A sorting algorithm that repeatedly finds the minimum element from an unsorted portion of the list and places it at the beginning.
Unit 7 refers to a specific section or module of study in the AP Computer Science A curriculum that focuses on topics such as arrays, ArrayLists, and searching algorithms.
Arrays: Arrays are data structures that store multiple values of the same type. They allow for efficient storage and retrieval of elements.
ArrayLists: ArrayLists are similar to arrays but have dynamic size, meaning they can grow or shrink as needed. They provide additional flexibility compared to regular arrays.
Searching Algorithms: Searching algorithms are methods used to find a specific element within a collection of data. Examples include linear search and binary search.
Algorithms are step-by-step procedures or instructions for solving problems or performing tasks. They provide clear instructions on how to solve problems efficiently.
Sorting Algorithms: Algorithms designed to arrange elements in a specific order, such as alphabetical or numerical order.
Searching Algorithms: Algorithms used to find specific elements within a collection of data.
Recursion: A programming technique where a function calls itself repeatedly until it reaches a base case.
Iterative code refers to programming constructs or algorithms that involve repetition using loops. It allows for executing a block of code multiple times until certain conditions are met.
Loop: A programming construct that repeats a block of code until certain conditions are met.
For Loop: A type of loop that iterates over an iterable object (such as lists) for a specified number of times.
While Loop: A type of loop that continues iterating as long as a given condition remains true.
Merge Sort is an efficient, comparison-based sorting algorithm that divides an unsorted list into smaller sublists, sorts those sublists recursively, and then merges them back together to obtain a sorted list.
Quick Sort: A divide-and-conquer sorting algorithm that selects a pivot element and partitions the array around it. It recursively sorts subarrays before and after the pivot.
Heap Sort: A comparison-based sorting algorithm that uses binary heaps to build a partially ordered tree structure which is then used for sorting.
Radix Sort: A non-comparative integer sorting algorithm that distributes data elements into buckets based on digits or significant places.
Control structures are programming constructs that determine the flow of execution in a program. They allow you to make decisions and repeat actions based on certain conditions.
Loops: Loops are control structures that allow you to repeat a block of code multiple times until a certain condition is met.
Conditional Statements: Conditional statements are control structures that execute different blocks of code based on whether a specific condition is true or false.
Branching: Branching is a type of control structure that allows your program to take different paths or branches based on certain conditions.
Abstraction is the process of simplifying complex systems by breaking them down into smaller, more manageable parts. Method writing refers to defining behaviors or actions that an object can perform.
Object-Oriented Programming (OOP): OOP is a programming paradigm that organizes code into objects and emphasizes reusability through concepts like inheritance and encapsulation.
Encapsulation/Class Writing: Encapsulation is the practice of hiding internal details and providing a public interface for interacting with an object. Class writing involves defining the blueprint or template for creating objects in OOP.
Polymorphism/Method Overriding: Polymorphism allows objects of different classes to be treated as objects of a common superclass. Method overriding refers to redefining a method in a subclass to provide its own implementation while maintaining the same method signature.
Encapsulation is the practice of hiding internal details and providing a public interface for interacting with an object. Class writing involves defining the blueprint or template for creating objects in object-oriented programming.
Object-Oriented Programming (OOP): OOP is a programming paradigm that organizes code into objects and emphasizes reusability through concepts like inheritance and abstraction.
Abstraction/Method Writing: Abstraction is the process of simplifying complex systems by breaking them down into smaller, more manageable parts. Method writing refers to defining behaviors or actions that an object can perform.
Inheritance/Subclassing: Inheritance allows one class to inherit properties and methods from another class. Subclassing refers to creating a new class based on an existing class, inheriting its attributes while adding additional features.
Inheritance is a concept in object-oriented programming where a class inherits the properties and behaviors of another class. It allows for code reuse and promotes the creation of hierarchical relationships between classes.
Encapsulation: Encapsulation is the practice of hiding internal details and providing access to only necessary information through methods. It helps maintain data integrity and protects sensitive information.
Superclass: A superclass is the parent class in an inheritance hierarchy. It serves as a blueprint for creating subclasses that inherit its properties and behaviors.
Subclass: A subclass is a child class that inherits properties and behaviors from its superclass. It can add additional features or override existing ones inherited from the superclass.
Data structures are ways to organize, store, and manipulate data efficiently. They provide different methods of accessing, inserting, deleting, or searching for data elements based on specific requirements.
Arrays: Arrays are fixed-size collections that store elements of the same type sequentially in memory. They offer fast access but limited flexibility in terms of resizing.
Linked Lists: Linked lists consist of nodes connected through pointers where each node holds a value and a reference to the next node. They allow dynamic memory allocation but have slower access times compared to arrays.
Stacks: Stacks follow the Last-In-First-Out (LIFO) principle where elements can only be inserted or removed from one end called the top. They are useful for tracking function calls or undo/redo operations.
Discrete math is a branch of mathematics that deals with countable and distinct objects. It focuses on topics like sets, logic, relations, functions, and combinatorics.
Logic and Proofs: Logic and proofs involve the study of formal reasoning, including deductive reasoning, symbolic logic, truth tables, and proof techniques such as direct proof, contrapositive proof, and proof by contradiction.
Probability: Probability is the branch of mathematics that studies uncertainty or randomness. It involves calculating the likelihood or chance that an event will occur based on mathematical models.
Combinatorics: Combinatorics is a branch of discrete math that deals with counting techniques and arrangements of objects.
Sets are collections of unique elements with no specific order. They do not allow duplicate values and provide operations like union, intersection, and difference.
Lists: Ordered collections that allow duplicate elements.
Venn diagrams: Diagrams used to visualize relationships between sets and their intersections.
Cardinality: The size or number of elements in a set.
Logic and proofs involve the study of formal reasoning, including deductive reasoning, symbolic logic, truth tables, and proof techniques such as direct proof, contrapositive proof, and proof by contradiction.
Discrete Math: Discrete math is a branch of mathematics that deals with countable and distinct objects. It focuses on topics like sets, logic, relations, functions, and combinatorics.
Inductive Reasoning: Inductive reasoning involves making generalizations based on specific observations or patterns.
Propositional Calculus: Propositional calculus is a formal system used in symbolic logic to represent statements using logical operators like AND (∧), OR (∨), NOT (¬), etc., allowing for precise analysis.
Probability is the branch of mathematics that studies uncertainty or randomness. It involves calculating the likelihood or chance that an event will occur based on mathematical models.
Discrete Math: Discrete math is a branch of mathematics that deals with countable and distinct objects. It focuses on topics like sets, logic, relations, functions, and combinatorics.
Statistics: Statistics involves collecting, analyzing, interpreting, and presenting data to make informed decisions or draw conclusions about a population.
Random Variables: Random variables are variables that take on different values based on the outcome of a random event. They are used to model uncertain quantities in probability theory.
State machines are computational models that consist of a set of states and transitions between those states. They are used to represent systems that change from one state to another based on inputs or events.
Finite Automaton: A type of state machine with a finite number of states and transitions.
Mealy Machine: A type of state machine where outputs depend on both the current state and input.
Moore Machine: A type of state machine where outputs depend only on the current state.
Graphs are data structures that consist of nodes (vertices) and edges, where the edges represent relationships between the nodes. They are used to model connections or relationships between different entities.
Adjacency Matrix: A way to represent a graph using a matrix where each cell represents whether there is an edge between two nodes.
Depth-First Search (DFS): An algorithm that explores as far as possible along each branch before backtracking in a graph.
Breadth-First Search (BFS): An algorithm that explores all the vertices of a graph in breadth-first order, i.e., it visits all the neighbors before moving on to their neighbors.
A data structure is a way of organizing and storing data in a computer so that it can be accessed and used efficiently. It provides a systematic way to manage and manipulate data.
Linked List: A linked list is a type of data structure where each element (node) contains both the actual data and a reference to the next node in the sequence.
Pointers: Pointers are variables that store memory addresses. They are commonly used in programming languages to manipulate and traverse different types of data structures.
Array: An array is another type of data structure that stores elements of the same type in contiguous memory locations. It allows for random access to its elements using an index.
Polymorphism refers to the ability of objects to take on multiple forms or have multiple types. In programming, it allows different objects to be treated as instances of a common superclass, enabling flexibility and extensibility.
Method Overriding: Method overriding occurs when a subclass provides its own implementation for a method that is already defined in its superclass. This allows for customization of behavior specific to each subclass.
Dynamic Binding: Dynamic binding refers to determining which implementation of an overridden method should be called at runtime based on the actual type of the object rather than its declared type. It allows for flexibility in method invocation.
Interface: An interface is a collection of abstract methods that define a contract for classes to implement. It enables polymorphism by providing a common set of methods that different classes can implement.
Hash maps are data structures that store key-value pairs, where each key is unique. They use a hash function to convert the key into an index in an array, allowing for efficient retrieval and insertion of values.
Arrays: Data structures that store elements in contiguous memory locations.
Hash functions: Algorithms that take an input and produce a fixed-size output (hash value).
Collision resolution: Techniques used when two keys produce the same hash value in a hash map.
Trees are hierarchical data structures consisting of nodes connected by edges. Each node has zero or more child nodes, except for the root node which has no parent. Trees are commonly used for organizing data in a hierarchical manner.
Binary trees: Trees where each node has at most two child nodes.
Depth-first search: A traversal algorithm that explores as far as possible along each branch before backtracking.
AVL trees: Balanced binary search trees that maintain a balanced height to ensure efficient operations.
Graphics involve creating visual representations using computers. It encompasses various techniques such as rendering 2D or 3D images, manipulating pixels, applying transformations, and simulating realistic effects like lighting and shadows.
Rendering: This term refers to the process of generating images or animations from models or descriptions using computer algorithms.
Pixels: These are the smallest units of an image that can be individually manipulated and displayed on a screen.
Transformations: In graphics, transformations involve changing the position, size, orientation, or shape of objects in a scene.
Artificial Intelligence (AI) refers to the development of computer systems capable of performing tasks that typically require human intelligence, such as speech recognition or decision-making. Machine Learning (ML), a subset of AI, involves training algorithms on large datasets to make predictions or take actions without being explicitly programmed.
Neural Networks: Neural networks are computational models inspired by the structure and function of biological neural networks in the brain. They are widely used in machine learning for tasks such as image recognition or natural language processing.
Deep Learning: Deep learning is a subfield of machine learning that focuses on training deep neural networks with multiple layers. It enables more complex representations and higher accuracy in solving intricate problems.
Data Mining: Data mining involves extracting useful information or patterns from large datasets using various techniques such as statistical analysis or machine learning algorithms. It plays a crucial role in AI and ML by providing valuable insights for decision-making processes.
Algorithm analysis is the process of evaluating the efficiency and performance of an algorithm. It involves analyzing factors such as time complexity, space complexity, and scalability to determine how well an algorithm will perform in different scenarios.
Time Complexity: This term refers to the amount of time it takes for an algorithm to run based on its input size.
Space Complexity: This term refers to the amount of memory or storage space required by an algorithm.
Scalability: This term refers to how well an algorithm can handle larger input sizes without a significant decrease in performance.
Programming language construction involves designing and implementing programming languages. It includes creating syntax rules, defining data types, and developing compilers or interpreters that translate code written in a specific language into machine-readable instructions.
Syntax: This term refers to the set of rules that define how statements are structured in a programming language.
Semantics: This term refers to the meaning behind statements written in a programming language.
Compiler/Interpreter: These terms refer to software tools that translate human-readable code into machine-executable instructions or interpret code directly without prior translation.
Web development refers to the process of creating and maintaining websites. It involves designing, coding, and implementing various elements such as web pages, user interfaces, and databases.
HTML: HTML stands for Hypertext Markup Language. It is the standard language used to create web pages by defining their structure and content.
CSS: CSS stands for Cascading Style Sheets. It is a style sheet language used to describe how HTML elements should be displayed on a webpage, including layout, colors, fonts, etc.
JavaScript: JavaScript is a programming language that allows developers to add interactivity and dynamic features to websites. It enables functions like form validation, animations, and interactive content.