Basic Types of Algorithms
Recursive Algorithms
Definition:
- An algorithm that calls itself in its definition.
- Recursive case a conditional statement that is used to trigger the recursion.
- Base case a conditional statement that is used to break the recursion.
What you need to know:
- Stack level too deep and stack overflow.
- If you've seen either of these from a recursive algorithm, you messed up.
- It means that your base case was never triggered because it was faulty or the problem was so massive you ran out of RAM before reaching it.
- Knowing whether or not you will reach a base case is integral to correctly using recursion.
- Often used in Depth First Search
Iterative Algorithms
Definition:
- An algorithm that is called repeatedly but for a finite number of times, each time being a single iteration.
- Often used to move incrementally through a data set.
What you need to know:
- Generally you will see iteration as loops, for, while, and until statements.
- Think of iteration as moving one at a time through a set.
- Often used to move through an array.
Recursion Vs. Iteration
- The differences between recursion and iteration can be confusing to distinguish since both can be used to implement the other. But know that,
- Recursion is, usually, more expressive and easier to implement.
- Iteration uses less memory.
- Functional languages tend to use recursion. (i.e. Haskell)
- Imperative languages tend to use iteration. (i.e. Ruby)
- Check out this Stack Overflow post for more info.
Pseudo Code of Moving Through an Array (this is why iteration is used for this)
Recursion | Iteration
----------------------------------|----------------------------------
recursive method (array, n) | iterative method (array)
if array[n] is not nil | for n from 0 to size of array
print array[n] | print(array[n])
recursive method(array, n+1) |
else |
exit loop |
Greedy Algorithm
Definition:
- An algorithm that, while executing, selects only the information that meets a certain criteria.
- The general five components, taken from Wikipedia:
- A candidate set, from which a solution is created.
- A selection function, which chooses the best candidate to be added to the solution.
- A feasibility function, that is used to determine if a candidate can be used to contribute to a solution.
- An objective function, which assigns a value to a solution, or a partial solution.
- A solution function, which will indicate when we have discovered a complete solution.
What you need to know:
- Used to find the optimal solution for a given problem.
- Generally used on sets of data where only a small proportion of the information evaluated meets the desired result.
- Often a greedy algorithm can help reduce the Big O of an algorithm.
Pseudo Code of a Greedy Algorithm to Find Largest Difference of any Two Numbers in an Array.
greedy algorithm (array)
var largest difference = 0
var new difference = find next difference (array[n], array[n+1])
largest difference = new difference if new difference is > largest difference
repeat above two steps until all differences have been found
return largest difference
This algorithm never needed to compare all the differences to one another, saving it an entire iteration.