Unit 10 covers recursion — methods that call themselves. Understanding recursion is essential for the AP exam, particularly for tracing, binary search, and merge sort.
Recursive method: calls itself with a smaller/simpler input. Base case: condition where recursion stops (returns directly). Recursive case: calls itself, moving toward base case. Without base case → StackOverflowError (infinite recursion). Each call gets its own stack frame with local variables. Example: factorial(n) = n × factorial(n-1), base: factorial(0) = 1.
Trace by tracking each call and its return value. Draw call stack. Recursive binary search: compare middle element, recurse on left or right half. Merge sort: split array in half recursively, merge sorted halves — O(n log n). Key insight: trust the recursion — if the recursive call works for smaller inputs, and you correctly combine results, it works for the full input.
Use recursion when: (1) the problem has a naturally recursive structure (trees, fractals, divide-and-conquer), (2) the recursive solution is much cleaner than iterative (merge sort, tree traversal), (3) subproblems are independent. Use iteration when: (1) simple repetition (counting, summing), (2) performance matters (recursion has overhead from stack frames), (3) deep recursion could cause stack overflow. On the AP exam, know both approaches but be comfortable with recursive tracing. Most exam recursion involves: factorial, fibonacci, binary search, merge sort, and string/array processing.
Book a Trial + Diagnostic session. Get a personalized Learning Path with clear milestones, tutor match, and a plan recommendation — all within 24 hours.
Book Trial + Diagnostic →