Week 7 – Hardcore Recursion | My Impressions So Far!

you may ask yourself what the hell is this recursion he talks about?  Well Recursion is a method of solving problems that involves breaking a problem down into smaller and smaller increments (subproblems) until you get to a small enough task that it can be to accomplished. Recursion involves a function calling itself. As opposed to iteration using for or while loops. You’re probably now thinking when would I use recursion? While it may not seem like much off the bat, recursion allows us to write efficient algorithms with much less code to solve problems that may otherwise be very difficult to program or even impossible. There are 3 rules of recursive functions:

  1. A recursive function must have a base case (when to stop)
  2. A recursive function must change its state and move toward the base case. (series of simplifications)
  3. A recursive function must call itself, recursively

In simpler terms recursion is “defining a problem in terms of itself”.  Recursive calls solve smaller problems of the same “flavour” and then combine those solutions to get the solution to the main problem.

For example lets consider at taking the sum of a list of integers.

def sum_list(lst: list)-> int:
    """
    >>>sum_list([1,3,5,7,9])
    25
    """
    total = 0
    for i in lst:
        total += i
    return total

I’ve broken down the step the non-recursive algorithm performs

total= (1+(3+(5+(7+9))))                                                                                                     total= (1+(3+(5+16)))                                                                                                         total= (1+(3+21))                                                                                                               total= (1+24)                                                                                                                     total= 25 Now I can solve the same problem with a recursive algorithm.

    def sum_list(numlst: list)-> int:
     """
     >>> sum_list([1,3,5,7,9])
     25
     """
     #base case one item in the list
     if len(numlst) == 0:
         return numlst[0]
     else:
         return numlst[0] + sum_list(numlst[1:])

"""
Now I can get really fancy on you and make it even more
elegant looking using list comprehension! #AlphaStatus
"""

def sum_list(lst: int)-> int:
    """
    >>>sum_list([1,3,5,7,9])
    25
    """
    return sum([sum_list(i) if isinstance(i, list) else i for i in lst])

We didn’t need recursion for that did we? But we could use it anyways! It’s important to remember that recursion is simply a different method to coding an algorithm. Some functions don’t even need recursion, such as this one above. However, with that being said a recursive approach comes in very handy (is useful) for a programmer who need to develop much more complex problems like the 4 stool Tower of Hanoi I wrote the algorithm for a few weeks ago. Some programmers may choose a recursive approach because it is just easier for them to understand, while some algorithms just go hand in hand with recursion because of the way they are designed such as traversing a tree like structure which we learned about in class last week. Recursion is a very puzzling concept to understood at first it took me hours of practice coding to finally feel comfortable implementing it.

“The human cost of writing, and maintaining, an algorithm that is naturally recursive in an iterative form is far higher than any cost a particular compiler or interpreter might add for running recursive functions.” – Danny Heap

Professor Heap taught he that you gotta just trust the recursive calls works  after tracing the simple cases. I would say the hardest part of the problem is recognizing a recursive pattern. The wonderful thing it is that you can use it in almost any language!

its been another great week in the life of a Computer Science Major! Stay Hungry, Stay Foolish!

yours truly,                                                                                                                                     – “CodeShark”

Week 5 – Wrap up of A1 !

This week in CSC148 we spent time looking at the details of our first assignment this semester. An advanced version of the classic game of the Tower of Hanoi, where the goal is to move a stack of disks of descending sizes from one peg to another, using three pegs.  The only rules are:

1. You’re only allowed to move one disk at a time, and,                                                           2. You cannot stack a bigger disk on top of a smaller one.

here’s where the excitement comes  Professor Danny,  changed the traditional Tower of Hanoi story around so we had to figure out the algorithm to optimally transfer Anne Hoy’s stacks of cheese, rather than discs from one stool to another, using four stools (the extra being her recent investment) to reduce the number of steps necessary for moving larger and larger piles of cheeses.  The optimal solution for the traditional Tower of Hanoi problem is said to have a run time of 2^n – 1.

“Ann Hoy kept her high-quality cheese stacked on stools, the largest rounds underneath the smaller rounds, to stop rats and mice from getting at them. Occasionally the stool holding the cheese would need some maintenance (for example, the legs would start to buckle under the weight), and Anne would shift the entire stack from one stool to another. Since she could only move a single (hundred-pound plus) round of cheese at one time, and she refused to stack a larger-diameter cheese round on a smaller one (the outer part of the larger cheese would droop) she used three stools: one was her destination for her entire stack of cheese, one was the source (which likely needed its legs reinforced), and the third was for intermediate stacking. Chaucer immortalized the complicated routine Anne endured, lugging rounds of cheese from stool to stool as “The tour of Anne Hoy.”

Prof Danny, really emphasized the importance of recursive functions to be used for the expected solution, as this assignment was a means to teach us how to use recursion. After days of frustrating sessions of coding I couldn’t wrap my head around how a simple solvable problem with 3 pegs can be made dramatically more difficult by slightly loosening one of the constraints (i.e 4 pegs).  After writing pages and pages of Psuedo code it suddenly hit me! I was thinking about how to implement the recursion too complexly, recursion an art an art where simple thinking is highly regarded. So pretty much my four stool function can call itself over and over again until it reaches a certain threshold (base case), where the all the cheeses are moved to the destination peg which allows the operation to terminate. This 4 stool solution required me to find the least number of moves required to move any given number of cheeses using 4 stools and pass that value into the recursive function. To me implementing this part was the certainly one of the more challenging aspects of this assignment. When I finally figured out the logic behind it I felt a great deal of satisfaction! I am now confident in my capabilities to implement recursive function. Who’s excited for assignment 2, I know I am!

Screen Shot 2014-02-18 at 12.14.26 PM

Screen Shot 2014-02-18 at 12.15.41 PM

9 moves is said to be the least number of moves to move 4 cheeses with 4 stools.

That is all for this week folks, Stay Hungry. Stay Foolish!

yours truly,                                                                                                                                     – “CodeShark”

Week 4 – More recursion yay!

After reading the instructions for Assignment 1,  I see that it will involve some hardcore recursion. I felt it would  be a smart idea to go and further my understanding of the concept, by working some exercises on CodeAcademy before I try to solve a 4 stool version of  Tower of Hanoi recursively.

I also learned from Professor Danny, this week that Python has a built-in module called Turtle that draws simple line graphics that can be manipulated on a set plane depending on what direction you’d like the Turtle object to point. We can also get fancy and all by changing the color of the Turtle or be mean and hide its tail, haha!  I like the Turtle class as I feel like it was designed solely for teaching recursion.

The recursion allowed us to pick an arbitrary number of lines we wanted… for i in range(n): and draw that  number of lines recursively and from each point of the previous recursion it bursts out 3 times.

Screen Shot 2014-02-08 at 9.10.22 PM

But after class I decided to and mess with the program and spice it up a little bit. I added a few new features 2 more colors to the list, I changed the range  to 5 and the position of the plane that the bursts happen. And voila I get this beauty down below. ^_^

Screen Shot 2014-02-08 at 9.07.02 PMThat my friends is the magic of the mighty recursion! I dont always use recursion, but when I do its beautiful!

That is all for this week folks, stay humble!

yours truly,                                                                                                                                     – “CodeShark”