Recursive Searching and Sorting - AP Computer Science A

1. What is tail recursion?

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

2. What happens in stack unwinding in recursion?

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

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

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

4. State the time complexity of recursive merge sort.

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

5. What is the best case time complexity of recursive quicksort?

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

6. What is the time complexity of recursive binary search?

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

7. What is the base case for a recursive Fibonacci sequence?

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

8. What is recursion in computer science?

   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.

9. What is a stack overflow in recursion?

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

10. What is the base case for a factorial function?

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

11. Find the result of factorial(3) using recursive definition.

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

12. What is the time complexity of recursive Fibonacci?

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

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

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

14. State the purpose of memoization in recursion.

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

15. What is a recursive call?

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

16. What is a recursive algorithm?

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

17. What is the time complexity of binary search using recursion?

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

18. What is the significance of the call stack in recursion?

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

19. Describe the role of a base case in recursion.

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

20. What is the iterative alternative to recursion?

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

21. Which sort algorithm uses recursion?

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

22. What is a recursive data structure?

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

23. What is the space complexity of recursive quicksort?

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

24. What is the worst case time complexity of recursive quicksort?

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

25. What is mutual recursion?

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

26. What is the key advantage of using recursion?

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

27. Find the result of fib(4) using recursive definition.

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

28. What is the space complexity of recursive Fibonacci with memoization?

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

Study these flashcards