Fruitful functions (2024)

Buy this book at Amazon.com

6.1Return values

Some of the built-in functions we have used, such as the mathfunctions, produce results. Calling the function generates avalue, which we usually assign to a variable or use as part of anexpression.

e = math.exp(1.0)height = radius * math.sin(radians)

All of the functions we have written so far are void; they printsomething or move turtles around, but their return value is None.

In this chapter, we are (finally) going to write fruitful functions.The first example is area, which returns the area of a circlewith the given radius:

def area(radius): temp = math.pi * radius**2 return temp

We have seen the return statement before, but in a fruitfulfunction the return statement includesan expression. This statement means: “Return immediately fromthis function and use the following expression as a return value.”The expression can be arbitrarily complicated, so we couldhave written this function more concisely:

def area(radius): return math.pi * radius**2

On the other hand, temporary variables like temp often makedebugging easier.

Sometimes it is useful to have multiple return statements, one in eachbranch of a conditional:

def absolute_value(x): if x < 0: return -x else: return x

Since these return statements are in an alternative conditional,only one will be executed.

As soon as a return statement executes, the functionterminates without executing any subsequent statements.Code that appears after a return statement, or any other placethe flow of execution can never reach, is called dead code.

In a fruitful function, it is a good idea to ensurethat every possible path through the program hits areturn statement. For example:

def absolute_value(x): if x < 0: return -x if x > 0: return x

This function is incorrect because if x happens to be 0,neither condition is true, and the function ends without hitting areturn statement. If the flow of execution gets to the endof a function, the return value is None, which is notthe absolute value of 0.

>>> print absolute_value(0)None

By the way, Python provides a built-in function called abs that computes absolute values.

6.2Incremental development

As you write larger functions, you might find yourselfspending more time debugging.

To deal with increasingly complex programs,you might want to try a process calledincremental development. The goal of incremental developmentis to avoid long debugging sessions by adding and testing onlya small amount of code at a time.

As an example, suppose you want to find the distance between twopoints, given by the coordinates (x₁, y₁) and (x₂, y₂).By the Pythagorean theorem, the distance is:

The first step is to consider what a distance function shouldlook like in Python. In other words, what are the inputs (parameters)and what is the output (return value)?

In this case, the inputs are two points, which you can representusing four numbers. The return value is the distance, which isa floating-point value.

Already you can write an outline of the function:

def distance(x1, y1, x2, y2): return 0.0

Obviously, this version doesn’t compute distances; it always returnszero. But it is syntactically correct, and it runs, which means thatyou can test it before you make it more complicated.

To test the new function, call it with sample arguments:

>>> distance(1, 2, 4, 6)0.0

I chose these values so that the horizontal distance is 3 and thevertical distance is 4; that way, the result is 5(the hypotenuse of a 3-4-5 triangle). When testing a function, it isuseful to know the right answer.

At this point we have confirmed that the function is syntacticallycorrect, and we can start adding code to the body.A reasonable next step is to find the differencesx₂ − x₁ and y₂ − y₁. The next version stores those values intemporary variables and prints them.

def distance(x1, y1, x2, y2): dx = x2 - x1 dy = y2 - y1 print 'dx is', dx print 'dy is', dy return 0.0

If the function is working, it should display 'dx is 3' and ’dy is 4’. If so, we know that the function is getting the rightarguments and performing the first computation correctly. If not,there are only a few lines to check.

Next we compute the sum of squares of dx and dy:

def distance(x1, y1, x2, y2): dx = x2 - x1 dy = y2 - y1 dsquared = dx**2 + dy**2 print 'dsquared is: ', dsquared return 0.0

Again, you would run the program at this stage and check the output(which should be 25).Finally, you can use math.sqrt to compute and return the result:

def distance(x1, y1, x2, y2): dx = x2 - x1 dy = y2 - y1 dsquared = dx**2 + dy**2 result = math.sqrt(dsquared) return result

If that works correctly, you are done. Otherwise, you mightwant to print the value of result before the returnstatement.

The final version of the function doesn’t display anything when itruns; it only returns a value. The print statements we wroteare useful for debugging, but once you get the function working, youshould remove them. Code like that is called scaffoldingbecause it is helpful for building the program but is not part of thefinal product.

When you start out, you should add only a line or two of code at atime. As you gain more experience, you might find yourself writingand debugging bigger chunks. Either way, incremental developmentcan save you a lot of debugging time.

The key aspects of the process are:

1. Start with a working program and make small incremental changes. At any point, if there is an error, you should have a good ideawhere it is.
2. Use temporary variables to hold intermediate values so you candisplay and check them.
3. Once the program is working, you might want to remove some ofthe scaffolding or consolidate multiple statements into compoundexpressions, but only if it does not make the program difficult toread.

6.3Composition

As you should expect by now, you can call one function fromwithin another. This ability is called composition.

As an example, we’ll write a function that takes two points,the center of the circle and a point on the perimeter, and computesthe area of the circle.

Assume that the center point is stored in the variables xc andyc, and the perimeter point is in xp and yp. Thefirst step is to find the radius of the circle, which is the distancebetween the two points. We just wrote a function, distance, that does that:

radius = distance(xc, yc, xp, yp)

The next step is to find the area of a circle with that radius;we just wrote that, too:

result = area(radius)

Encapsulating these steps in a function, we get:

def circle_area(xc, yc, xp, yp): radius = distance(xc, yc, xp, yp) result = area(radius) return result

The temporary variables radius and result are useful fordevelopment and debugging, but once the program is working, we canmake it more concise by composing the function calls:

def circle_area(xc, yc, xp, yp): return area(distance(xc, yc, xp, yp))

6.4Boolean functions

Functions can return booleans, which is often convenient for hidingcomplicated tests inside functions. For example:

def is_divisible(x, y): if x % y == 0: return True else: return False

It is common to give boolean functions names that sound like yes/noquestions; is_divisible returns either True or Falseto indicate whether x is divisible by y.

Here is an example:

>>> is_divisible(6, 4)False>>> is_divisible(6, 3)True

The result of the == operator is a boolean, so we can write thefunction more concisely by returning it directly:

def is_divisible(x, y): return x % y == 0

Boolean functions are often used in conditional statements:

if is_divisible(x, y): print 'x is divisible by y'

It might be tempting to write something like:

if is_divisible(x, y) == True: print 'x is divisible by y'

But the extra comparison is unnecessary.

Exercise3Write a function is_between(x, y, z) thatreturns True if x ≤ y ≤ z or False otherwise.

6.5More recursion

We have only covered a small subset of Python, but you mightbe interested to know that this subset is a completeprogramming language, which means that anything that can becomputed can be expressed in this language. Any program ever writtencould be rewritten using only the language features you have learnedso far (actually, you would need a few commands to control deviceslike the keyboard, mouse, disks, etc., but that’s all).

Proving that claim is a nontrivial exercise first accomplished by AlanTuring, one of the first computer scientists (some would argue that hewas a mathematician, but a lot of early computer scientists started asmathematicians). Accordingly, it is known as the Turing Thesis.For a more complete (and accurate) discussion of the Turing Thesis,I recommend Michael Sipser’s book Introduction to theTheory of Computation.

To give you an idea of what you can do with the tools you have learnedso far, we’ll evaluate a few recursively defined mathematicalfunctions. A recursive definition is similar to a circulardefinition, in the sense that the definition contains a reference tothe thing being defined. A truly circular definition is not veryuseful:

frabjous:

An adjective used to describe something that is frabjous.

If you saw that definition in the dictionary, you might be annoyed. Onthe other hand, if you looked up the definition of the factorialfunction, denoted with the symbol !, you might get something likethis:

This definition says that the factorial of 0 is 1, and the factorialof any other value, n, is n multiplied by the factorial of n−1.

So 3! is 3 times 2!, which is 2 times 1!, which is 1 times0!. Putting it all together, 3! equals 3 times 2 times 1 times 1,which is 6.

If you can write a recursive definition of something, you can usuallywrite a Python program to evaluate it. The first step is to decidewhat the parameters should be. In this case it should be clearthat factorial takes an integer:

def factorial(n):

If the argument happens to be 0, all we have to do is return 1:

def factorial(n): if n == 0: return 1

Otherwise, and this is the interesting part, we have to make arecursive call to find the factorial of n−1 and then multiply it byn:

def factorial(n): if n == 0: return 1 else: recurse = factorial(n-1) result = n * recurse return result

The flow of execution for this program is similar to the flow of countdown in Section5.8. If we call factorialwith the value 3:

Since 3 is not 0, we take the second branch and calculate the factorialof n-1...

Since 2 is not 0, we take the second branch and calculate the factorial ofn-1...

Since 1 is not 0, we take the second branch and calculate the factorialof n-1...

Since 0 is 0, we take the first branch and return 1without making any more recursive calls.

The return value (1) is multiplied by n, which is 1, and theresult is returned.

The return value (1) is multiplied by n, which is 2, and theresult is returned.

The return value (2) is multiplied by n, which is 3, and the result, 6,becomes the return value of the function call that started the wholeprocess.

Here is what the stack diagram looks like for this sequence of functioncalls:

The return values are shown being passed back up the stack. In eachframe, the return value is the value of result, which is theproduct of n and recurse.

In the last frame, the localvariables recurse and result do not exist, becausethe branch that creates them does not execute.

6.6Leap of faith

Following the flow of execution is one way to read programs, butit can quickly become labyrinthine. Analternative is what I call the “leap of faith.” When you come to afunction call, instead of following the flow of execution, you assume that the function works correctly and returns the rightresult.

In fact, you are already practicing this leap of faith when you usebuilt-in functions. When you call math.cos or math.exp,you don’t examine the bodies of those functions. You justassume that they work because the people who wrote the built-infunctions were good programmers.

The same is true when you call one of your own functions. Forexample, in Section6.4, we wrote a function called is_divisible that determines whether one number is divisible byanother. Once we have convinced ourselves that this function iscorrect—by examining the code and testing—we can use the functionwithout looking at the body again.

The same is true of recursive programs. When you get to the recursivecall, instead of following the flow of execution, you should assumethat the recursive call works (yields the correct result) and then askyourself, “Assuming that I can find the factorial of n−1, can Icompute the factorial of n?” In this case, it is clear that youcan, by multiplying by n.

Of course, it’s a bit strange to assume that the function workscorrectly when you haven’t finished writing it, but that’s whyit’s called a leap of faith!

6.7One more example

After factorial, the most common example of a recursivelydefined mathematical function is fibonacci, which has thefollowing definition¹:

Translated into Python, it looks like this:

def fibonacci (n): if n == 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2)

If you try to follow the flow of execution here, even for fairlysmall values of n, your head explodes. But according to theleap of faith, if you assume that the two recursive callswork correctly, then it is clear that you getthe right result by adding them together.

6.8Checking types

What happens if we call factorial and give it 1.5 as an argument?

>>> factorial(1.5)RuntimeError: Maximum recursion depth exceeded

It looks like an infinite recursion. But how can that be? There is abase case—when n == 0. But if n is not an integer,we can miss the base case and recurse forever.

In the first recursive call, the value of n is 0.5.In the next, it is -0.5. From there, it gets smaller(more negative), but it will never be 0.

We have two choices. We can try to generalize the factorialfunction to work with floating-point numbers, or we can make factorial check the type of its argument. The first option iscalled the gamma function² and it’s alittle beyond the scope of this book. So we’ll go for the second.

We can use the built-in function isinstance to verify the typeof the argument. While we’re at it, we can also make sure theargument is positive:

def factorial (n): if not isinstance(n, int): print 'Factorial is only defined for integers.' return None elif n < 0: print 'Factorial is not defined for negative integers.' return None elif n == 0: return 1 else: return n * factorial(n-1)

The first base case handles nonintegers; thesecond catches negative integers. In both cases, the program printsan error message and returns None to indicate that somethingwent wrong:

>>> factorial('fred')Factorial is only defined for integers.None>>> factorial(-2)Factorial is not defined for negative integers.None

If we get past both checks, then we know that n is positive orzero, so we can prove that the recursion terminates.

This program demonstrates a pattern sometimes called a guardian.The first two conditionals act as guardians, protecting the code thatfollows from values that might cause an error. The guardians make itpossible to prove the correctness of the code.

6.9Debugging

Breaking a large program into smaller functions creates naturalcheckpoints for debugging. If a function is not working, there arethree possibilities to consider:

• There is something wrong with the arguments the functionis getting; a precondition is violated.
• There is something wrong with the function; a postconditionis violated.
• There is something wrong with the return value or theway it is being used.

To rule out the first possibility, you can add a print statementat the beginning of the function and display the values of theparameters (and maybe their types). Or you can write codethat checks the preconditions explicitly.

If the parameters look good, add a print statement before eachreturn statement that displays the return value. Ifpossible, check the result by hand. Consider calling thefunction with values that make it easy to check the result(as in Section6.2).

If the function seems to be working, look at the function callto make sure the return value is being used correctly (or usedat all!).

Adding print statements at the beginning and end of a functioncan help make the flow of execution more visible.For example, here is a version of factorial withprint statements:

def factorial(n): space = ' ' * (4 * n) print space, 'factorial', n if n == 0: print space, 'returning 1' return 1 else: recurse = factorial(n-1) result = n * recurse print space, 'returning', result return result

space is a string of space characters that controls theindentation of the output. Here is the result of factorial(5) :

 factorial 5 factorial 4 factorial 3 factorial 2 factorial 1 factorial 0 returning 1 returning 1 returning 2 returning 6 returning 24 returning 120

If you are confused about the flow of execution, this kind ofoutput can be helpful. It takes some time to develop effectivescaffolding, but a little bit of scaffolding can save a lot of debugging.

6.10Glossary

temporary variable:

A variable used to store an intermediate value ina complex calculation.

dead code:

Part of a program that can never be executed, often becauseit appears after a return statement.

None:

A special value returned by functions thathave no return statement or a return statement without an argument.

incremental development:

A program development plan intended toavoid debugging by adding and testing onlya small amount of code at a time.

scaffolding:

Code that is used during program development but isnot part of the final version.

guardian:

A programming pattern that uses a conditionalstatement to check for and handle circ*mstances thatmight cause an error.

6.11Exercises

def b(z): prod = a(z, z) print z, prod return proddef a(x, y): x = x + 1 return x * ydef c(x, y, z): sum = x + y + z pow = b(sum)**2 return powx = 1y = x + 1print c(x, y+3, x+y)

def first(word): return word[0]def last(word): return word[-1]def middle(word): return word[1:-1]

Exercise7A number, a, is a power of b if it is divisible by band a/b is a power of b. Write a function calledis_power that takes parameters a and band returns True if a is a power of b.Note: you will have to think about the base case.

1

Seewikipedia.org/wiki/Fibonacci_number.

2

Seewikipedia.org/wiki/Gamma_function.

3

Seewikipedia.org/wiki/Ackermann_function.

4

This exercise isbased on an example from Abelson and Sussman’s Structure andInterpretation of Computer Programs.