Chapter 6  Fruitful functions 第 6 章 有返回值的函数

本页译自 Think Python 2e（Allen B. Downey）· Chapter 6 Fruitful functions。代码块保留英文原文不翻译；正文段段对照，中文块可用右下角按钮隐藏。

6.1 Return values 6.1 返回值

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

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

All of the functions we have written so far are void; they print something 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 None, which returns the area of a circle with the given radius:

We have seen the None00 statement before, but in a fruitful function the None00 statement includes an expression. This statement means: "Return immediately from this function and use the following expression as a return value." The expression can be arbitrarily complicated, so we could have written this function more concisely:

On the other hand, temporary variables like None often make debugging easier.

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

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

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

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

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

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

Exercise 1

Write a None000 function that returns x if None0003, x if None00, and x0 if None0004.

6.2 Incremental development 6.2 增量开发

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

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

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

distance = √(x₂ − x₁)² + (y₂ − y₁)²

The first step is to consider what a None0005 function should look 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 represent using four numbers. The return value is the distance, which is a floating-point value.

Already you can write an outline of the function:

Obviously, this version doesn't compute distances; it always returns zero. But it is syntactically correct, and it runs, which means that you can test it before you make it more complicated.

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

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

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

If the function is working, it should display None00055 and None00056. If so, we know that the function is getting the right arguments and performing the first computation correctly. If not, there are only a few lines to check.

Next we compute the sum of squares of x0 and x0:

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

If that works correctly, you are done. Otherwise, you might want to print the value of None00 before the return statement.

The final version of the function doesn't display anything when it runs; it only returns a value. The None0 statements we wrote are useful for debugging, but once you get the function working, you should remove them. Code like that is called scaffolding because it is helpful for building the program but is not part of the final product.

When you start out, you should add only a line or two of code at a time. As you gain more experience, you might find yourself writing and debugging bigger chunks. Either way, incremental development can 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 idea where it is.
2. Use temporary variables to hold intermediate values so you can display and check them.
3. Once the program is working, you might want to remove some of the scaffolding or consolidate multiple statements into compound expressions, but only if it does not make the program difficult to read.

1. 从一个能运行的程序出发，做小的增量改动。任何时候出错，你都该大致知道错在哪里。
2. 用临时变量保存中间值，以便显示并检查它们。
3. 程序能正常运行后，你可以去掉部分脚手架，或把多条语句合并成复合表达式，但前提是这不会让程序难以阅读。

Exercise 2

Use incremental development to write a function called None00072 that returns the length of the hypotenuse of a right triangle given the lengths of the two legs as arguments. Record each stage of the development process as you go.

6.3 Composition 6.3 组合

As you should expect by now, you can call one function from within 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 computes the area of the circle.

Assume that the center point is stored in the variables x0 and x0, and the perimeter point is in x0 and x0. The first step is to find the radius of the circle, which is the distance between the two points. We just wrote a function, None0007, that does that:

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

Encapsulating these steps in a function, we get:

The temporary variables None00 and None00 are useful for development and debugging, but once the program is working, we can make it more concise by composing the function calls:

6.4 Boolean functions 6.4 布尔函数

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

It is common to give boolean functions names that sound like yes/no questions; None00093

returns either None or None0 to indicate whether x is divisible by x.

Here is an example:

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

Boolean functions are often used in conditional statements:

It might be tempting to write something like:

But the extra comparison is unnecessary.

Exercise 3

Write a function None00109








that returns None if x ≤ y ≤ z or None0 otherwise.

6.5 More recursion 6.5 更多递归

We have only covered a small subset of Python, but you might be interested to know that this subset is a complete programming language, which means that anything that can be computed can be expressed in this language. Any program ever written could be rewritten using only the language features you have learned so far (actually, you would need a few commands to control devices like the keyboard, mouse, disks, etc., but that's all).

Proving that claim is a nontrivial exercise first accomplished by Alan Turing, one of the first computer scientists (some would argue that he was a mathematician, but a lot of early computer scientists started as mathematicians). 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 the Theory of Computation.

To give you an idea of what you can do with the tools you have learned so far, we'll evaluate a few recursively defined mathematical functions. A recursive definition is similar to a circular definition, in the sense that the definition contains a reference to the thing being defined. A truly circular definition is not very useful:

vorpal:

An adjective used to describe something that is vorpal.

vorpal（原文自造词）：

一个用来形容「vorpal 的事物」的形容词。

If you saw that definition in the dictionary, you might be annoyed. On the other hand, if you looked up the definition of the factorial function, denoted with the symbol !, you might get something like this:

0! = 1
n! = n(n−1)!

This definition says that the factorial of 0 is 1, and the factorial of 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 times 0!. 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 usually write a Python program to evaluate it. The first step is to decide what the parameters should be. In this case it should be clear that None00115 takes an integer:

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

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

The flow of execution for this program is similar to the flow of None00120 in Section 5.8. If we call None00121 with the value 3:

Since 3 is not 0, we take the second branch and calculate the factorial of x00...

由于 3 不等于 0，我们走第二个分支，计算 x00 的阶乘……

Since 2 is not 0, we take the second branch and calculate the factorial of x00...

由于 2 不等于 0，我们走第二个分支，计算 x00 的阶乘……

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

由于 0 确实等于 0，我们走第一个分支，返回 1，不再做任何递归调用。

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

返回值（1）乘以 n（即 1），得到结果并返回。

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

返回值（1）乘以 n（即 2），得到结果并返回。

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 whole process.

Figure 6.1: Stack diagram.

The return values are shown being passed back up the stack. In each frame, the return value is the value of None00, which is the product of x and None001.

In the last frame, the local variables None001 and None00 do not exist, because the branch that creates them does not execute.

6.6 Leap of faith 6.6 信仰之跃

Following the flow of execution is one way to read programs, but it can quickly become labyrinthine. An alternative is what I call the "leap of faith." When you come to a function call, instead of following the flow of execution, you assume that the function works correctly and returns the right result.

In fact, you are already practicing this leap of faith when you use built-in functions. When you call None0013 or None0013, you don't examine the bodies of those functions. You just assume that they work because the people who wrote the built-in functions were good programmers.

The same is true when you call one of your own functions. For example, in Section 6.4, we wrote a function called None00142

that determines whether one number is divisible by another. Once we have convinced ourselves that this function is correct—by examining the code and testing—we can use the function without looking at the body again.

The same is true of recursive programs. When you get to the recursive call, instead of following the flow of execution, you should assume that the recursive call works (yields the correct result) and then ask yourself, "Assuming that I can find the factorial of n−1, can I compute the factorial of n?" In this case, it is clear that you can, by multiplying by n.

Of course, it's a bit strange to assume that the function works correctly when you haven't finished writing it, but that's why it's called a leap of faith!

6.7 One more example 6.7 再举一例

After None00144, the most common example of a recursively defined mathematical function is None00145, which has the following definition (see None00146


































):

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n−1) + fibonacci(n−2)

Translated into Python, it looks like this:

If you try to follow the flow of execution here, even for fairly small values of n, your head explodes. But according to the leap of faith, if you assume that the two recursive calls work correctly, then it is clear that you get the right result by adding them together.

6.8 Checking types 6.8 类型检查

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

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

In the first recursive call, the value of x 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 None00160 function to work with floating-point numbers, or we can make None00161 check the type of its argument. The first option is called the gamma function and it's a little beyond the scope of this book. So we'll go for the second.

We can use the built-in function None00164 to verify the type of the argument. While we're at it, we can also make sure the argument is positive:

The first base case handles nonintegers; the second catches negative integers. In both cases, the program prints an error message and returns None to indicate that something went wrong:

If we get past both checks, then we know that n is positive or zero, 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 that follows from values that might cause an error. The guardians make it possible to prove the correctness of the code.

In Section 11.3 we will see a more flexible alternative to printing an error message: raising an exception.

6.9 Debugging 6.9 调试

Breaking a large program into smaller functions creates natural checkpoints for debugging. If a function is not working, there are three possibilities to consider:

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

• 函数收到的实参有问题；某个前置条件被违反了。
• 函数本身有问题；某个后置条件被违反了。
• 返回值或用它的方式有问题。

To rule out the first possibility, you can add a None0 statement at the beginning of the function and display the values of the parameters (and maybe their types). Or you can write code that checks the preconditions explicitly.

If the parameters look good, add a None0 statement before each None00 statement that displays the return value. If possible, check the result by hand. Consider calling the function with values that make it easy to check the result (as in Section 6.2).

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

Adding print statements at the beginning and end of a function can help make the flow of execution more visible. For example, here is a version of None00176 with print statements:

None0 is a string of space characters that controls the indentation of the output. Here is the result of None00180

:

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

6.10 Glossary 6.10 术语表

temporary variable:

A variable used to store an intermediate value in a complex calculation.

dead code:

Part of a program that can never be executed, often because it appears after a None00 statement.

None:

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

incremental development:

A program development plan intended to avoid debugging by adding and testing only a small amount of code at a time.

scaffolding:

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

guardian:

A programming pattern that uses a conditional statement to check for and handle circumstances that might cause an error.

临时变量：

在复杂计算中用来保存中间值的变量。

死代码：

程序中永远无法被执行到的部分，通常因为它出现在 None00 语句之后。

None：

由那些没有 return 语句、或 return 语句不带实参的函数返回的特殊值。

增量开发：

一种程序开发方案，旨在通过每次只添加并测试少量代码来避免调试。

脚手架：

在程序开发过程中使用、却不属于最终版本的代码。

卫式条件（guardian pattern）：

一种编程模式，用条件语句检查并处理可能引发错误的情形。

6.11 Exercises 6.11 习题

Exercise 4

Draw a stack diagram for the following program. What does the program print? Solution: None00188

































.

Exercise 5

The Ackermann function, A(m, n), is defined:
A(m, n) =
        n+1              if m = 0
        A(m−1, 1)         if m > 0 and n = 0
        A(m−1, A(m, n−1))  if m > 0 and n > 0.
See None00191




































. Write a function named x00 that evaluates Ackermann's function. Use your function to evaluate None00193, which should be 125. What happens for larger values of x and x? Solution: None00196





























.

Exercise 6

A palindrome is a word that is spelled the same backward and forward, like "noon" and "redivider". Recursively, a word is a palindrome if the first and last letters are the same and the middle is a palindrome.

The following are functions that take a string argument and return the first, last, and middle letters:

We'll see how they work in Chapter 8.

1. Type these functions into a file named None00204
   
   
   and test them out. What happens if you call None00 with a string with two letters? One letter? What about the empty string, which is written x0 and contains no letters?
2. Write a function called None00207
   
   
   that takes a string argument and returns None if it is a palindrome and None0 otherwise. Remember that you can use the built-in function x00 to check the length of a string.

1. 把这些函数敲进一个名为 None00211
   
   
   的文件并测试。如果你用含有两个字母的字符串调用 None00 会怎样？一个字母呢？空字符串（写作 x0，不含任何字母）又如何？
2. 写一个名为 None00214
   
   
   的函数，接收字符串实参，若是回文则返回 None，否则返回 None0。记住你可以用内置函数 x00 检查字符串长度。

Solution: None00218



































.

Exercise 7

A number, a, is a power of b if it is divisible by b and a/b is a power of b. Write a function called None0022 that takes parameters x and x and returns None if x is a power of x. Note: you will have to think about the base case.

Exercise 8

The greatest common divisor (GCD) of a and b is the largest number that divides both of them with no remainder.

One way to find the GCD of two numbers is based on the observation that if r is the remainder when a is divided by b, then gcd(a, b) = gcd(b, r). As a base case, we can use gcd(a, 0) = a.

Write a function called x00 that takes parameters x and x and returns their greatest common divisor.

Credit: This exercise is based on an example from Abelson and Sussman's Structure and Interpretation of Computer Programs.