AP Computer Science a Flashcards: Recursive Searching And Sorting

What this deck covers

This deck focuses on Recursive Searching And Sorting, giving you a quick way to review the definitions, rules, and examples that matter most for AP Computer Science a.

How to use these flashcards

Work through these flashcards in short sessions. Try to answer each prompt before flipping the card, then revisit any cards you miss until the explanation feels automatic.

Flashcard 1: What is tail recursion?

Answer: A recursion where the recursive call is the last operation. Can be optimized by compilers into iterative loops to save stack space.

Flashcard 2: What happens in stack unwinding in recursion?

Answer: The call stack is cleared as function calls return in reverse order. Functions complete in reverse order of how they were called.

Flashcard 3: What is a common application of recursion in search problems?

Answer: Binary search. Efficiently searches sorted arrays by recursively eliminating half the elements.

Flashcard 4: State the time complexity of recursive merge sort.

Answer: $O(n \text{ log } n)$. Divides array in half, sorts recursively, then merges sorted halves.

Flashcard 5: Describe the role of a base case in recursion.

Answer: It prevents infinite recursion by stopping further recursive calls. Essential terminating condition that provides a direct answer without further recursion.

Flashcard 6: What is the time complexity of binary search using recursion?

Answer: $O(\text{log } n)$. Halves the search space with each recursive call.

Flashcard 7: What is the best case time complexity of recursive quicksort?

Answer: $O(n \text{ log } n)$. When pivot consistently divides array into balanced partitions.

Flashcard 8: What is the time complexity of recursive binary search?

Answer: $O(\text{log } n)$. Eliminates half the search space with each recursive call.

Flashcard 9: What is the base case for a recursive Fibonacci sequence?

Answer: $F(0) = 0$, $F(1) = 1$. These are the first two Fibonacci numbers that stop the recursive sequence.

Flashcard 10: What is the space complexity of recursive quicksort?

Answer: $O(\text{log } n)$ for balanced partitions. Each recursive call adds a new frame to the call stack.

Flashcard 11: What is recursion in computer science?

Answer: Recursion is a method where the solution to a problem depends on solutions to smaller instances. This defines the fundamental principle of breaking down complex problems into simpler versions.

Flashcard 12: What is tail recursion?

Answer: A recursion where the recursive call is the last operation. Can be optimized by compilers into iterative loops to save stack space.

Flashcard 13: What is a common application of recursion in search problems?

Answer: Binary search. Efficiently searches sorted arrays by recursively eliminating half the elements.

Flashcard 14: What is a stack overflow in recursion?

Answer: A stack overflow occurs when there are too many nested recursive calls. Happens when recursion depth exceeds the call stack's memory limit.

Flashcard 15: What is the base case for a factorial function?

Answer: $n = 0$, returning 1. By definition, $0! = 1$ and this stops the recursive multiplication.

Flashcard 16: What is the best case time complexity of recursive quicksort?

Answer: $O(n \text{ log } n)$. When pivot consistently divides array into balanced partitions.

Flashcard 17: Find the result of factorial(3) using recursive definition.

Answer:

1. $3! = 3 \times 2 \times 1 = 6$

Flashcard 18: What is the time complexity of recursive Fibonacci?

Answer: $O(2^n)$. Each call branches into two more calls, creating exponential growth.

Flashcard 19: Find the result of a recursive binary search for 3 in [1, 2, 3, 4].

Answer: Found at index 2. Binary search finds 3 by comparing with middle elements recursively.

Flashcard 20: State the purpose of memoization in recursion.

Answer: Memoization stores results of expensive function calls to avoid redundant calculations. Converts exponential time algorithms into linear time by caching results.

Flashcard 21: What is a recursive call?

Answer: A function call where the function calls itself with modified arguments. This creates the recursive loop that reduces problem size with each iteration.

Flashcard 22: What is a recursive algorithm?

Answer: An algorithm that solves a problem by solving smaller instances recursively. Uses the divide-and-conquer principle by calling itself on smaller inputs.

Flashcard 23: What is the time complexity of binary search using recursion?

Answer: $O(\text{log } n)$. Halves the search space with each recursive call.

Flashcard 24: What is the significance of the call stack in recursion?

Answer: Holds information about active subroutines of a computer program. Tracks nested function calls and manages local variables for each recursion level.

Flashcard 25: Describe the role of a base case in recursion.

Answer: It prevents infinite recursion by stopping further recursive calls. Essential terminating condition that provides a direct answer without further recursion.

Flashcard 26: What is the iterative alternative to recursion?

Answer: Loops (such as for, while). Uses explicit loops instead of function calls to avoid stack overhead.

Flashcard 27: What is the significance of the call stack in recursion?

Answer: Holds information about active subroutines of a computer program. Tracks nested function calls and manages local variables for each recursion level.

Flashcard 28: Which sort algorithm uses recursion?

Answer: Merge sort. Divides arrays recursively, then merges sorted subarrays back together.

Flashcard 29: What is a recursive data structure?

Answer: A data structure that contains instances of itself. Examples include linked lists, trees, and graphs with self-similar structures.

Flashcard 30: What is the space complexity of recursive quicksort?

Answer: $O(\text{log } n)$ for balanced partitions. Each recursive call adds a new frame to the call stack.

Flashcard 31: What is the worst case time complexity of recursive quicksort?

Answer: $O(n^2)$. Occurs when pivot is always the smallest or largest element.

Flashcard 32: What is mutual recursion?

Answer: Two or more functions that call each other. Creates indirect recursion where functions depend on each other cyclically.

Flashcard 33: What is the key advantage of using recursion?

Answer: Simplifies code for problems that can be divided into similar sub-problems. Natural fit for problems with recursive structure like trees and mathematical sequences.

Flashcard 34: Find the result of factorial(3) using recursive definition.

Answer:

1. $3! = 3 \times 2 \times 1 = 6$

Flashcard 35: Find the result of fib(4) using recursive definition.

Answer:

1. $F(4) = F(3) + F(2) = 2 + 1 = 3$

Flashcard 36: What is the space complexity of recursive Fibonacci with memoization?

Answer: $O(n)$. Stores computed values to avoid recalculating the same Fibonacci numbers.

Flashcard 37: State the time complexity of recursive merge sort.

Answer: $O(n \text{ log } n)$. Divides array in half, sorts recursively, then merges sorted halves.

Flashcard 38: What is a recursive data structure?

Answer: A data structure that contains instances of itself. Examples include linked lists, trees, and graphs with self-similar structures.