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.