Recursion: every key term you need

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.