CISC-121
20130207

More Recursion

We have seen that recursion can be used in the search problem: to search a sorted list for a target value, we look at the value in the middle of the list - if that is not what we are looking for, we search either the left side or the right side of the list.  Since searching half of a list is essentially the same problem as searching the whole list, recursion is a natural choice for the implementation of this algorithm.

Now consider the problem of multiplication.  Of course in Python and every other programming language, multiplying numbers is a built-in arithmetic function.  We can simply write  value = 7*9 and value will be assigned the value 63.  However suppose that this built-in function did not exist.  Suppose the only arithmetic operations available are addition, multiply by 2, and divide by 2.  (In fact this is not such a strange assumption - these three operations are among the most basic and essential operations built into computer hardware.  Multiplication is a much higher level operation.)

Could we multiply 7 by 9 using just addition?  A natural idea is to look at 7*9 as 7+7+7+7+7+7+7+7+7, which we can compute using a for loop:


value = 0
for i in range(9):
    value += 7
print value

or in general to add two integers x and y, where y is not negative:

value = 0
for i in range(y):
    value += x
print value
  

We can turn this into a recursive function.  This is a very good exercise when you are learning recursion - take any simple loop and see if there is a way to replace it by a recursive function.  It won't always be a good idea, but the practice will pay off in the long run.  Learning to understand recursion thoroughly is one of the most important steps in learning to think like a computer scientist.


def rec_mult(x,y):
    # base case
    if y == 0:
        return 0
    else:
        # recursive part
        return x + rec_mult(x,y-1)


# main program
value = rec_mult(7,9)
print value

I cannot recommend strongly enough that you should trace through the execution of this recursive function to convince yourself that it correctly computes the value of 7*9.

In this case the recursive function and the for loop do exactly the same thing, and in practice there is no reason not to use the for loop.  


Now in our hypothetical computer, we are allowed not only addition, but also multiplication by 2 and division by 2.  How can we use those to speed up the process of computing x*y?
 
There is an ancient method of multiplication that has been discovered independently in several parts of the world.  It goes like this:  Start two columns of numbers, with x at the top of the first column and y at the top of the second.  Now add another row by doubling x and halving y (rounding down).  Continue doing this until the value in the y column is 1.

For example if x = 5 and y = 13, the columns would look like this

                5            13
                10            6            (remember we round down when we divide y by 2)
                20            3       
                40            1            (3/2 rounded down = 1)

Now look at the rows where the y value is odd - in this example, we look at the first, third and fourth row.   Add together the x values on those rows:  5 + 20 + 40.  The result is 65,  which is exactly 5*13 !!!!!

This looks like magic.  Let's try it again with x = 6 and y = 47

                  6              47
                12              23
                24              11
                48                5
                96                2
              192                1


Once again the y values are odd on  all but one row, and when we add the x values from the rows where y is odd we get 6+12+24+48+192 = 282  ... which is indeed 6*47

Don't worry if you don't see why this works right now - we will come back to it later in the course - we will see that  representing x and y in base 2 notation makes it completely obvious why this algorithm works.  For now we will look at how to implement this algorithm.  First consider a loop.  A for loop is not appropriate because we do not know how many times the loop should execute.  It makes more sense to use a while loop that will continue as long as y is >= 1

x = 7
y = 11
value = 0
while y >= 1:
    if y % 2 == 1:        # this tests to see if y is odd
        value += x
    x = x*2
    y = y/2                  # integer division automatically rounds down
print value

Work through this a time or two to make sure you understand it, then consider this recursive version:

def clever_mult(x,y):
    if y == 0:
        return 0
    elif y % 2 == 1:
        return x + clever_mult(x*2, y/2)
    else:
        return clever_mult(x*2,y/2)

value = clever_mult(7,11)

By now you can guess what I will say next: you should trace through the execution of clever_mult so that you can see exactly how the recursion works.

Once again the while loop is probably more efficient than the recursive function in real time because function calls involve some overhead time to create new frames on the execution stack.  However, and this is a crucial point - they are both more efficient than the for loop and/or the recursive function that we started with.  The for loop, when computing 6*47, would have looped 47 times.  The "clever multiplication" algorithm as we saw above, only creates 6 rows of values, and adds together 5 of them.  Even allowing time for the doubling of x and halving of y, this is much faster.