AP Computer Science A Unit 10: Recursion
Study recursive methods, base case, recursive vs iterative, merge sort, binary search with exam-format practice and rubric-based scoring.
Start AP CSA Practice · Full Study Guide
AP and Advanced Placement are trademarks of College Board. AimFive is not affiliated with or endorsed by College Board.
Inside This Unit: The Full Breakdown
Recursion is a technique where a method calls itself to solve a problem by breaking it into smaller subproblems. This unit covers recursive thinking, base cases, tracing recursive calls, and recursive algorithms like binary search and merge sort.
Why it matters
Recursion appears on every AP CSA exam in both multiple-choice and free-response sections. Understanding how the call stack works, identifying base and recursive cases, and tracing through recursive execution are essential skills.
Key concepts
- A recursive method calls itself with a smaller or simpler input, progressing toward a base case.
- The base case stops recursion and returns a value directly without making another recursive call.
- Each recursive call adds a frame to the call stack; frames resolve in reverse order (LIFO).
- Binary search recursively halves the search space, achieving O(log n) efficiency on sorted data.
Recursive Thinking
Recursion solves a problem by reducing it to a smaller version of itself. Every recursive method needs at least one base case (a condition that stops the recursion) and at least one recursive case (a call to itself with a simpler input). For example, factorial(n) returns 1 if n <= 1 (base case) and n * factorial(n-1) otherwise. Missing or incorrect base cases cause infinite recursion and a StackOverflowError. The key insight is trusting that the recursive call correctly solves the smaller problem.
Tracing Recursive Methods
To trace a recursive method, follow each call down to the base case, then work backward as each call returns its result. Drawing a call tree helps visualize the process. For factorial(4): factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1), which returns 1. Then results propagate back: 2*1=2, 3*2=6, 4*6=24. The AP exam tests tracing with specific inputs and asks for the return value or the number of recursive calls made.
Recursive Algorithms
Binary search recursively divides a sorted array in half: compare the target to the middle element, then search the left or right half. This runs in O(log n) time compared to O(n) for linear search. Merge sort recursively splits an array into halves, sorts each half, and merges them back together in O(n log n) time. The AP exam expects you to understand these algorithms conceptually, trace through them, and recognize when recursion is more appropriate than iteration.
AP exam tip
When tracing recursion on the AP exam, draw a tree or stack diagram. Start from the initial call, expand each recursive call, find the base case, then work backward to compute the final result.
Connections to other units
- Unit 3: Recursion is an alternative to iteration — many loop algorithms can be rewritten recursively.
- Unit 5: Recursive methods can process arrays by passing a reduced index range with each call.
- Unit 7: 2D array problems like maze solving or flood fill are naturally recursive.
