Vocab
- Big O notation for Hash map, Binary Search, Single loop, Nested Loop
- Big O notation describes the set of all algorithms that run no worse than a certain speed, no better than a certain speed, and at a certain speed
- Shows the number of operations it will perform
Recursion
- a recursive method is a method that calls itself
- contains at least one base case that halts recursion and once recursive call
- each recursive call has its own local variables
- parameter values take progress of recursive progress
- recursion can be replaced with an iterative and give same result
- Recursion can traverse String, array, and ArrayList objects
Binary Search (way to use recursion)
- find midpoint and choose upper or lower half of section over and over agin until number is located
- code to do this would use recursion and call the search function in itself
Merge Sort (way to use recursion)
- divide and conquer algortih to Sort ArrayList
- divies array in halves and then calls itself for the two halves in order to sort them
- mergeds the two sorted halves into one list
Recursion Tree
- recursion trees are a method for visualizing each recurisve case until the base case is reached
- in order for recursion block to finish, there must be some speicial case in which they dont call themselves (base case)