[Tutor] parsing--is this right? [function evaluation / errors for fun and profit]

[Danny Yoo]

On Tue, 11 Jun 2002, Paul Tremblay wrote:

> Recursion is both intuitive and counter-intuitive. For example, Derrick
> showed a fairly simple example using a factorial. But what happens to
> the return in this line?
>
> return n * fact( n-1 )
>
> You think of return as getting one value, but the return somehow has to
> wait and build up a value.

Yes, it has to evaluate the value of 'n * fact(n-1)', but this is not so
different from other expressions that use functions as little helpers.



Let's take one example of how Python builds up values, a hypotenuse
calculator:

###
def hypotenuse(side1, side2):
    return math.sqrt(square(side1) + square(side2))

def square(x): return x * x
###

This hypotenuse() function tells us how long a diagonal to a right
triangle would be, if we knew the lengths of the other two sides.  In
order for hypotenuse() function to work, it has to pass off some of the
work over to the square() function.


In fact, we can actually see this delegation in action if we deliberately
put a bug into square():

###
>>> import math
>>> def hypotenuse(side1, side2):
...     return math.sqrt(square(side1) + square(side2))
...
>>> def square(x):
...     return a * b
...
>>> hypotenuse(3, 4)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 2, in hypotenuse
  File "<stdin>", line 2, in square
NameError: global name 'a' is not defined
###

If we look at the traceback error, it actual says something like "While I
was trying to compute hypotenuse, to do that, I had to do a square()ing...
but while I was trying to compute square, I ran into a problem." So
hypotenuse() actually passes the torch to squares()  first.  Once
square()'s done, then square() can 'return' the torch back to
hypotenuse().  That's why both functions are listed in this "traceback".



Here's a more dramatic example of the way Python calculates: let's reuse
that factorial() example, but let's be mischevious again: we'll put in a
fatal flaw that makes factorial() break down if we try to calculate
factorial(0):

###
>>> def factorial(x):
...     if x == 0:
...         print "I'm going to break down."
...         print 0 / 0   ## This is deliberate.
...     return x * factorial(x-1)
...
>>> factorial(0)
I'm going to break down.
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 4, in factorial
ZeroDivisionError: integer division or modulo by zero
###

Yup, it breaks down predictably.  But what happens if we put larger values
of 'x' in there?


###
>>> factorial(4)
I'm going to break down.
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 5, in factorial
  File "<stdin>", line 5, in factorial
  File "<stdin>", line 5, in factorial
  File "<stdin>", line 5, in factorial
  File "<stdin>", line 4, in factorial
ZeroDivisionError: integer division or modulo by zero
###

The error message is subtly different:  there's a bunch more lines of
Python complaining!  And that's because to calculate factorial(4), Python
sees that it has to calculate factorial(3)... but to calculate
factorial(3), it has to first calculate factorial (2)... etc.  So
factorial() shows up multiple times, once for every time it had to use
itself as a helper.


If you ever have time to browse through a bookstore, try flipping through
Douglas Hofstadter's book, "Godel Escher Bach".  There's a very cool
chapter called "Little Harmonic Labyrinth", and it captures the idea of
recursion very well.


Gotta sleep now.  Hope this was helpful!