first look at algorithms and recursion
4 min readAug 3, 2020
- Tell us about something you learned this week.
i learned a little bit about how recursion works in javascript, and programming in general to an extent. that having a function pass itself as an argument is the basic principle of recursion. and that it also needs a way to exit the loop, lest thine crash thoust browser. - What are the pros and cons of immutability?
How can you achieve immutability in your own code?
i really don’t know how to answer this question without being very vague. so here goes. immutability is simply the inability to be changed. in javascript, strings and numbers are immutable. obviously this is really useful, since we don’t want to change the value of 1 every time we happen to say arr.length -1. and obviously it would be really inconvenient if all my variables were immutable, and once i declared one could never do anything more with it.
as for how i could achieve immutability in my own code, one principle which i stumbled upon is to use pure functions. a pure function is a function whose results always depend on its arguments while never changing anything beyond its own scope. but this is just another way of saying to code efficiently and mindfully. - What are Divide and Conquer algorithms? Describe how they work. Can you give any common examples of the types of problems where this approach might be used?
divide and conquer algorithms recursively break a problem down into smaller and smaller bits until it can do a single thing to each bit while keeping track as it does so. sort algorithms in particular can break down an array of numbers until the elements are in groups of two and can be compared to one another on an individual basis, and then groups the numbers back together according to the condition set by the function. - How do insertion sort, heap sort, quick sort, and merge sort work?
What are the key advantages of insertion sort, quick sort, heap sort and merge sort? Discuss best, average, and worst case time and memory complexity.
insertion sort works by moving down the array one by one and shifting the smallest value (if sorting in ascending order) it finds to the front, and recursively doing so from the position right after the last sorted item.
heap sort works by building an upside tree of nodes out of a given array (a heap). it then “max-heapifies” the tree by moving down the tree node-by-node, swapping child nodes out with their parent node every time the child node is a greater number. each one of these swaps represents their index switching with one another until the greatest value is the root of the tree. then the root is swapped with the last item (the smallest value) in the tree and removed (as it is now sorted), with the process continuing until no further nodes remain.
quick sort picks a (pretty much) random pivot within an array, and then compares each other number to it. lesser numbers go to the “left” and greater numbers to the “right.” this divides and conquers each “left” and “right” until there’s only singular items left which are joined by together, now in order.
merge sort works very similarly to insertion sort but it divides everything into smaller and smaller groups until the smallest groups (of two) can be compared to each other and built back together but in order. this type of sort is very symmetrical, as it breaks down an array into its smallest pieces before putting it back together again in the inverted order of which it was broken down. - Explain the difference between mutable and immutable objects.
immutable objects are superior to mutable objects for many reasons. you should try to build code out of immutable objects whenever possible, in order to avoid things like side effects, shared state, and impure functions. these are all things that lead to your code having a harder time being debugged, amended, or in general working correctly under duress. as an example, imagine you’re given const x = { val: 2 }. then imagine you wanted to manipulate the value inside the object. instead of const x1 = () => x.val += 1;, you could write const x1 = x => Object.assign({}, x, { val: x.val + 1}). in the first example, you have mutated x. in the second example, you create an object copy that represents the original value, and can be manipulated as much as you like without mutating the original data. click the link for a great article on this stuff by Eric Elliot. - What are the three laws of algorithm recursion? Describe them in your own words and what they mean to you.
a. A recursive algorithm must have a base case.
b. A recursive algorithm must change its state and move toward the base case.
c. A recursive algorithm must call itself, recursively.
so a base case is where the algorithm wants to end up, so that it can exit its recursion. so in a recursive algorithm that counted down to 0, you would put a conditional gate in there like:function countdownFrom(n) {
console.log(n)
if (n > 0) countdownFrom(n -1)
}
console.log(countdownFrom(10))
you’ll also notice that b) is taken care of as well with the n-1, as each time the function runs, it changes its state by -1 and moves toward the base case. and c) is taken care of by virtue of countdownFrom() being called from within the function itself. also, i’m sorry about the formatting of the function i can’t seem to get medium to cooperate and let me tab the declaration block contents. :(
