Code ~> Python ~> Recursion

Today, I spent some time doing MITx: 6.00x Introduction to Computer Science and Programming on edx. The course is in Python, so I am polishing my Python syntax in the process. :)

As the title suggests, the topic today was on recursion. This basically means breaking a problem into a smaller easier problem to solve, then solving it from at point. I am going to use a simple example to explain this concept. In functions, the functioned being defined is applied within it's own definition. 

Let us pretend that Python did not have a build in function to do multiplication, but had a build in function to do addition. We are doing to use the addition function, so come up with our own multiplication function.

We will first solve the problem using an iterative function, then will use a recursive function.

So to break down multiplication to simple terms, when we multiply a number n by a number m, we are simply adding up m times of n, or adding up m copies of n. So this means, n * m = n + n  (m -1). That makes the problem much simpler! Let us break it down one more step: n + n  (m -1) = n + n + n (m - 2).  We could go on doing this until it is the basic addition I mentioned earlier. Let us now do this in Python.

Iterative function

def multiplierI(a, b):
    """takes two positive integers, and returns the product of the two"""
    result = 0
    while b > 0:
        result += a
        b -= 1
    return result

Recursive function

def multiplierR(a ,b):
    """takes two positive integers and returns the product of the two"""
    if b == 1:
        return n
    elif b == 0:
        return 0
    else:
        return a  + multiplierR(a, b - 1)
So how does this function work, you may ask.

Let me call it with two arguments, 1 and 2.
multiplierR(1, 2)

I shall now attempt to explain the different environments that are involved in the recursive function so that you see that even though there are no assigned state variables (eg result in the iterative function), that are clearly being updated, we will not be stuck it an infinite loop. I know that what's going on is pretty straight forward to programmers, even beginners, but I have fun explaining stuff, so here goes.

When we call multiplierR(1, 2), the interpreter looks up multiplierR() in the global environment, and sees that it is a procedure object taking two parameters. It creates another environment where it binds a(the first parameter) to 1 and b(the second parameter) to 2. In the body of multiplierR(), we check whether b is 1 or 0, it's neither cause it's bound to 2. We then move down to else statement which returns a added to another call to multiplierR(), this time passing in (a, b-1), which in our case is (1, 1). The interpreter again looks up multiplierR(), finds the procedure object. It create a third environment where it binds a(the first parameter) to 1, and b(second parameter) to 1. In the body, we check if b is equal to 1, yes it is, so we return a, which is 1 in our case. Remember, that this second call if from the point where it is called within the function itself. This is the line a + multiplierR(a, b - 1). multiplierR(a, b - 1) returns a, breaking this down to a + a, which is 1 + 1 in our case.

I have used small integers to avoid going over all the process again and again. But please not that b in the case where b is a large number, say 5, the return value of the call to multiplierR() in all the different environments are there, though not accessible to us, so when b is finally 1, it'll be able to look up the other values in the different environments and add them up. It does this naturally, well, the code does this naturally, so that we do not have to do this - result += a, over and over again. Although, it's basically the same idea.

So there you have it. The recursive function is much cleaner! :)

Disclaimer: I am writing this at 2.06am, and I am not planning to test this code before publishing, so please feel free to comment and correct any error in my code and/or explanation. :)