Week of Feb.23.2013 - Recursion

Recursion to say the least is a difficult concept to wrap your head around.  Mainly because it involves the process of having a function to call itself, which is a common method of solving problems, especially problems with multiple depths, such as having to compute the sum of a given list of lists, or multi-dimensional arrays.  Each time a function calls itself, the program uses up more ram, and in fact is a common way for hackers to get access to your computer due to the fact that if you continually call a recessive function, you may get a heap error, that is when your sandboxed memory reaches the top of the heap.

In order to avoid a heap error, all recursive functions must have a base case, or else it will go on forever, and force the OS to crash the program.  After the base case, there is usually the condition(s) for which the function calls itself.

Let's start by creating a basic factorial recursive function.  First we would need to decide the base case.  We know that 0! is equal to 1, so we can say that if 'n' – n being the parameter of the function – is equal to 0, then the function shall return 1, otherwise we want to return n*factorial(n-1).

def factorial(n):
    if n == 0:
        return 1
    else:
        return n*factorial(n-1)

Tracing through a few examples, factorial(0) goes straight to the base case, and returns 1.  Let's trace something slightly more difficult.
factorial(2) goes straight to the else, giving us 2*factorial(2-1), evaluating factorial(1) gives us 1*factorial(0), which we evaluate factorial(0), reaching the base case, which returns 1, then the previously called function returns 1*1, and eventually returning 2*1, giving us that factorial(2) equals to 2.

Week of Feb.02.2013

Last week seemed to have focused heavily on recursion and one class was based on specifically solving TOAH's problem with three stools, where as our assignment we must solve it with four stools.  Overall, most of the weekend was spent on completing the assignment, and some difficulties that occurred was understanding what to actually do on the assignment, due to the overwhelming amount of code that was given to us.  After a few hours on the first night, we were able to figure out what we were supposed to do, and completing the first two steps took about an hour.  On day two, we were able to complete step 5, and finalize the assignment.  Step 5 was the hardest due to the fact that tracing such a large program recursively was quite difficult.