8.1 Recursion: Introduction
Algorithm: a sequence of steps for solving a problem
Recursive algorithm: an algorithm that breaks the problem into smaller subproblems and applies the same algorithm to solve the smaller subproblems
Base case: when a function performs an action instead of recursing
8.2 Recursive methods
NOTE: recursion can be direct (a function calls itself) or indirect (functions call each other)
8.3 Recursive algorithms
Fibonacci numbers
Binary search
8.4 Recursive definitions
8.5 Creating a recursive method
Creating a recursive method:
- Base case
- Recursive case
8.6 Stack overflow
Stack frame: memory allocated for a function call on the stack
Stack overflow: a stack frame extends beyond the memory region allocated for the stack
8.7 Recursive math methods
8.8 Recursive exploration of all possibilities
8.9 Adding output statements for debugging
8.10 Analyzing the time complexity of recursive algorithms
Recursion tree: a visual diagram of an operation done by a recursive function that separates operations done directly by the function and operations done by recursive calls
Node: a structure that stores data and has links to other nodes
8.11 Searching and algorithms
8.12 Recursive algorithm: Search
NOTE: integer rounding can cause infinite recursion when searching higher, while keeping the midpoint when searching lower simplifies the base case
8.13 Binary search
NOTE: for even , binary search takes comparisons below the minimum and above the maximum (worst case)