Week 7 - Recursion

Recursion, a method of solving problems by breaking down the big problems into several smaller instances of the same problem. These smaller instances are called base cases. Base cases are the simplest version of bigger problem that you are trying to solve using recursion. There many are examples of this when using recursion to solve problems that involve nested structures such as binary search trees and nested lists. For example, say I wanted to find the max of the [1, [2, 3]]. The simplest instance aka the base case of the problem is just applying the built-in method max on a single non-nested list.. So the function would cycle through the original list [1, [2, 3]], but when it reaches to the item [2, 3], it will call itself to find the max of that list which is the nested list. [2, 3] falls under a base case and the max of the list which can be found using max() is 3. The function would then replace [2, 3] with 3. So the list is now just [1, 3] and the function would simply find the max() and return 3.
By breaking down the problems into its base cases, it allows to solve many versions of the same problem if they have all the same base cases. Therefore, this technique is really useful to use because it reduces the amount of code. Many of the big problems can be simplified to its base cases and allows you to be lazy and solve the big problem with relatively few lines of code. Being lazy is of the greatest skills of a computer scientist. Also, the code is really efficient in that it doesn't require lines and lines of code. A problem can be solved recursively simply using 1 line of code. Therefore, recursion is really useful technique.
A prime example of using recursion to solve the problem at hand which was moving cheese across the four stools in A. The stools were a nested list where each stool was list that was inside a big list that holds all the stools. Therefore, this was a problem that could be solved very easily using recursion because there were base cases that could be used to solve the bigger problem. The base cases were moving a cheese from origin to destination, and moving two cheese from origin to the destination. By breaking the overall big problem of moving several cheeses across 4 stools into the base case of either moving 1 cheese or 2 cheeses, the solution of the problem was slowly built up. What I mean by the solution was built was that because you know how to move 2 cheeses, you know how to move 3 cheeses and because you know how to move 3 cheese you know how to move 4 cheeses is which just moving 3 cheese plus moving 4th cheese i.e one cheese from the origin to the destination.