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.