Recursion: every key term you need

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.

More AP Computer Science A guides

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