Recursive Searching and Sorting - AP Computer Science A

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

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

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

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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