Recursion: every key term you need (+ practice quiz)

More AP Computer Science A guides

• Primitives
• Using Objects
• Boolean Expressions
• Loops
• Writing Classes

Recursion

Function calls itself. Breaks problem into smaller subproblems. Must have base case (stop) and recursive case.

Base Case

Condition stopping recursion. Without it, infinite recursion → StackOverflowError. Example: if (n==0) return 1;

Recursive Case

Function calls itself with smaller input. Moves toward base case. Example: return n * factorial(n-1);

Call Stack

Tracks function calls. Each recursive call adds frame to stack. When base case reached, stack unwinds.

Factorial

n! = n * (n-1)!. Base: 0! = 1. Example: 5! = 5*4*3*2*1. Elegant recursive solution.

Fibonacci

fib(n) = fib(n-1) + fib(n-2). Base: fib(1)=1, fib(0)=0. Exponential time; use memoization to optimize.

Memoization

Cache results to avoid recomputation. fib(5) calculates fib(3) multiple times; store result, reuse.

Binary Search (Recursive)

Divide search space in half. Base: not found or found. Recursive: search left or right half. O(log n).

Tree Traversal

Visit each node exactly once. Preorder: root, left, right. Inorder: left, root, right. Postorder: left, right, root.

String Recursion

Process strings character-by-character. Example: reverse string recursively or check palindrome.

Backtracking

Explore all possibilities; abandon path if constraint violated. Example: Sudoku solver, maze solver.

Unit 10 Summary

Recursion: function calls itself; needs base case and recursive case. Useful for divide-and-conquer, tree traversal, backtracking.

Base Case

The input for which the method returns without recursing. Every recursive method needs at least one; missing or unreachable base cases cause StackOverflowError.

Recursive Case

The branch that calls the method on a smaller or simpler input, moving toward the base case. Progress must be guaranteed for termination.

Call Stack Frames

Each call gets its own copy of parameters and local variables. Work after the recursive call resumes when the deeper call returns, in reverse order of calls.

Tracing Recursion

Write each call with its arguments, resolve the deepest one first, then substitute results upward. For print-then-recurse vs recurse-then-print, output order differs.

Recursion vs Iteration

Any recursion in the AP subset can be rewritten as a loop; the exam asks you to read and trace recursion, not write it from scratch (except in reasoning about equivalence).

Factorial

fact(n) = n * fact(n - 1) with fact(0) = 1. Depth n; fact(5) makes 6 calls including the base case.

Fibonacci Recursion

fib(n) = fib(n-1) + fib(n-2) with fib(0)=0, fib(1)=1. Two recursive calls per non-base call causes exponential call counts; fib(5) makes 15 calls.

Sum of Digits Recursively

sum(n) = n % 10 + sum(n / 10) with sum(0) = 0. Mirrors the iterative digit loop.

String Recursion

Typical shape: base case on empty or one-char string; recursive case handles the first char and recurses on substring(1). Reversal appends the first char after the recursive result.

Recursion on Arrays with an Index Parameter

Helper methods carry the current index: sum(arr, i) = arr[i] + sum(arr, i + 1) with base i == arr.length returning 0.

Binary Search Preconditions

Requires sorted data. Compare the middle element to the target; discard the half that cannot contain it. Works iteratively or recursively.

Binary Search Efficiency

Each comparison halves the remaining range, so at most about log2(n) + 1 comparisons: 1,000 elements need at most 10; 1,000,000 need at most 20.

Binary Search Middle Index

mid = (low + high) / 2 uses integer division. After comparing, set low = mid + 1 or high = mid - 1; forgetting the +1/-1 can loop forever.

Merge Sort Structure

Split the array in half, recursively sort each half, then merge two sorted halves in linear time. Recursion depth is about log2(n).

Merge Step

Walk two sorted sequences with two indices, always copying the smaller current element into a temporary array, then copy any leftovers.

Merge Sort Efficiency

About n × log2(n) work: log2(n) levels, each doing n element copies. Much faster than selection or insertion sort for large n, at the cost of extra memory.

Sort Comparison Table

Selection: always ~n^2/2 comparisons, ~n swaps. Insertion: n-1 comparisons best case, ~n^2/2 worst. Merge: ~n log n always.

Counting Recursive Calls

Count the initial call plus every call it triggers. For a method that recurses on n - 1 down to 0, calls = n + 1; for halving recursions, roughly log2(n) + 1.

Infinite Recursion Symptoms

StackOverflowError at runtime. Causes: base case never reached (recursing on n + 1 instead of n - 1), or base case placed after the recursive call.

Recursion with Multiple Base Cases

Methods like fib or a palindrome check need two base cases (length 0 and 1). Missing one lets an index go negative or a substring call throw.

Progress Toward the Base Case

Every recursive call must strictly reduce the problem in a way that reaches a base case, or the stack will exhaust and throw StackOverflowError.

Multiple Base Cases

Fibonacci needs two, at n = 0 and n = 1, because a single base case would leave one branch recursing forever.

Stack Frame Contents

Each pending call stores its own parameters, local variables, and return address, which is why deep recursion consumes memory proportional to its depth.

Work After the Recursive Call

Code placed after the call runs on the way back up, which is what makes printing after recursion produce reversed output.

Tree Recursion Cost

Two recursive calls per level create about 2^n total calls, which is why naive Fibonacci becomes unusable well before n = 50.

Linear Recursion Cost

One recursive call per level with constant work gives n total calls, matching the cost of the equivalent loop.

Recursion Depth vs Call Count

Naive Fibonacci has depth only n but makes exponentially many calls, so depth and total work are separate measures.

Helper With an Extra Parameter

An index or accumulator parameter carries state through the recursion, letting a clean public method delegate to a private recursive helper.

Recursive Array Traversal

Base case is index equal to length; the recursive case processes one element and recurses on index + 1.

Divide and Conquer Halving

Splitting the input in half at each level produces about log2(n) levels, which is the source of binary search and merge sort efficiency.

Binary Search Requires Sorted Data

Discarding half the range is only valid when order guarantees the target cannot be in the discarded half.

Binary Search Comparison Count

Roughly log2(n) + 1 comparisons, so doubling the data adds only one comparison — 1000 items need about 10.

Binary Search Termination

The recursion ends when low exceeds high, which signals that the target is absent and -1 should be returned.

Merge Sort Splitting Phase

The array is halved recursively until single-element pieces remain, which are trivially sorted by definition.

Merge Sort Combining Phase

Adjacent sorted halves are merged in linear time, and the log2(n) levels of merging give n log n total work.

Merge Sort Space Cost

Merging needs temporary storage proportional to n, unlike selection and insertion sort, which sort in place.

Sorting Comparison Summary

Selection and insertion sort are quadratic in the worst case; merge sort is n log n on every input, which is why it dominates for large arrays.

Reversing a String Recursively

Return the reverse of the substring from index 1 followed by the first character, with the empty string as the base case.

Mutual Recursion Beyond the Subset

Two methods can call each other, as in an even/odd pair, but AP questions restrict themselves to a method calling itself.

Tracing With a Call Table

Writing each call's arguments and pending return value in a table is the reliable way to evaluate a recursive expression by hand.

Converting Recursion to Iteration

Linear recursion converts directly to a loop with an accumulator, while tree recursion requires an explicit stack or memoization.

Recursive Sum of Digits

Base case n < 10 returns n; otherwise return n % 10 + sumDigits(n / 10), so each level removes one digit.