Recursion Lesson
Recursion
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
Introduction to Recursion
- a method that calls itself
- contains at least one base case that halts recursion and once recursive call
- each recursive call has own local variables
- parameter values take progress of recursive process
- a recursion can be replaced with an iterative and give the same result
- recursion can traverse string, array and arraylist objects
Merge Sort
- can be used to sort arraylists
- Uses a divide and conquer algorithm
- divides the array into halves and then calls itself for the two different halves in order to sort them
- merges the two sorted halves into one list
- Merging Values into One Sorted Array
- copy the original elements into a temporary array
- work from left to right in each virtual array to
- compare element and return them to the correct order in the original array