程序员入伙书——函数初步

以前的几个章节里，大家一定常见到print(…)、range(…)、max(…)之类的结构，它们是什么呢？

它们叫函数。不用管这个名字听起来多么奇怪，和数学上的函数、方程的概念多么不同，先接受这个名字，后面我会说这个名字的来历。

比如说，我们在《程序在干什么？》一节的最后一段举过一个求平方根的例子，后来在《初涉算法》一节讲解过它。就拿这个程序为例，如果现在我想求(根号2 + 根号3) x (根号5 – 根号7)，该怎么写程序？

当然我们可以把这个例子复制粘贴四遍，第一遍求根号2，第二遍求根号3，第三遍求根号5，第四遍求根号七，然后用这四个中间结果算出最后的值。

这个思路能干活，可就是直觉太傻太啰嗦。四段程序只有喂给它们的数字的差别，实在是太浪费了。所以人们想，可以引入数学上的函数y = f(x)概念，定义好这个函数的公式（f）之后，把参数（x）喂给它，让同一段代码对参数进行运算，运算结果放在y里，这样岂不节约？

好主意！我们现在把求平方根的算法定义成一个函数：

>>> def mysqrt(n):
    high = max(1, n)
    low = 0
    while True:
        result = (high + low) / 2
        if abs(result * result - n)  < n * 1E-8:
            break
        if result * result > n:
            high = result
        else:
            low = result
    return result

>>>

这段程序里最关键的是第一行，以关键字def引导的函数名mysqrt，其后以括号包围要传递给这个函数的参数n，最后是冒号表示：以下的缩进内容是用来定义这个函数的算法。

最后一行return result也很重要，见到return语句时，程序就会返回到使用函数的那个位置，在相应的mysqrt(x)的地方，放上本次运行得到的result值。这个值被称为返回值。

说得再多不如实际做一次：

>>> (mysqrt(2) + mysqrt(3)) * (mysqrt(5) - mysqrt(7))
-1.2889720732435594
>>>

瞧，结果出来了！在这个四则运算里，mysqrt函数的那段程序总共被运行了四次，每进入这段程序一次，n都被代入一个不同的值：2、3、5、7。每次运行到return result一句时，就返回这个四则运算，直到所有的mysqrt(x)都拿到自己的返回值为止。程序使用函数的过程，叫做调用。

一些老一代的编程语言对返回值比较看重，有返回值的才有资格叫“函数”（Function），没有返回值的被称为Subroutine（子例程）或者Procedure（过程），FORTRAN语言和PASCAL语言就是这样的，这两种语言里，对函数和子例程/过程的定义，使用的语法是不同的。就我个人见过的语言里，第一个统一了这两种概念的是C语言，C语言认为不返回值的例程只是函数的一种特例，因此把它们统称为函数。在英语世界里，这个统一过程顺理成章，十分自然，因为Function这个词可以译为“功能”，不管是返回值的还是不返回值的，叫功能总是没错的。而汉语世界的读者就很难接受不返回值的“函数”的概念。没事，多看看就习惯了。

函数可以有很多参数，就是说，括号里可以放很多值。例如Python语言的自带函数max()、min()、print()都可以接受多个参数。max(3, 12, 4, 5)，顾名思义，返回所有参数最大的那个，12。而min(3, 12, 4, 5)则相反，返回最小的3。这两个函数都接受至少两个参数——求单个数字的最大值或最小值是没有意义的。求绝对值的函数abs()则接受正好一个参数，多也不行少也不行，理由也很明显。

函数也可以没有参数。例如：

>>> string = input()
A quick brown fox jumps over the lazy dog.
>>> string
'A quick brown fox jumps over the lazy dog.'
>>>

这个例子里，Python自带的input()函数读取你所做的键盘单行输入，把这个输入的行放到返回值里面，然后你就可以拿这个返回值做后期处理了。

来写个判断一个数字是否为质数（素数）的函数：

>>> def isprime(n):
    if not isinstance(n, int) or n < 2:    # 如果n不是整数，或小于2
        return False                       # 返回“假”
    if n == 2:                             # 如果n等于2
        return True                        # 是质数，返回“真”
    for i in range(2, int(n ** 0.5) + 2):  # i从2循环到根号n，检测：
        if n % i == 0:                     # 如果n能被i整除
            return False                   # 则不是质数，返回“假”
    return True                            # 被以上循环筛选过的是质数
>>>

我已经把注释写在每行代码后头，希望大家能看懂。然后咱们做几个实验：

>>> isprime(1)
False
>>> isprime(2)
True
>>> isprime(3)
True
>>> isprime(4)
False
>>> isprime(5)
True
>>> isprime(6)
False
>>> isprime(7)
True
>>> isprime(8)
False
>>> isprime(9)
False
>>> isprime(10)
False
>>> isprime(11)
True
>>>

结果还挺对的，是吧？我们再狂野一些，拿这个函数验证一下哥德巴赫猜想——任意大于2的偶数可以表示为两个质数的和。注意，我们是要验证，不是证明。这个验证，是指定一个区间，让程序把这个区间里的偶数逐个拆分成两个质数，从而局部验证这个猜想。因为整数没有上限，所以我们无法真正做到穷举所有整数——假如我们能做到，这个猜想就算是被证明了，而不是现在这个半死不活的样子。

验证的思路很简单，对于任何一个偶数n，我们使用变量i做从2到n/2的循环，当我们发现i和n-i同时为质数时，对于n来说，哥德巴赫猜想就算是成立的。

>>> def goldbach(n):
    if n % 2 != 0 or n < 4:                  # 如果n不是偶数，或小于4
        return None                          # 既不算证明也不算推翻
    for i in range(2, n // 2 + 1):           # i从2循环到n的一半
        if isprime(i) and isprime(n - i):    # 如果i和n-i都是质数
            print(n, ' = ', i, ' + ', n - i) # 打印加法算式
            return True                      # 猜想对整数n成立
    return False   # 否则猜想被此整数推翻，事实上到目前为止，这句话从未被执行

>>>

好了，我们已经写好了两个函数：isprime(n)检查数字n是不是质数，goldbach(n)通过调用isprime()，来检查哥德巴赫猜想对数字n是否成立。现在我们就来实际跑一遍：

>>> for n in range(4, 52, 2):     # 从4循环到50，每次增量为2，循环：
    if goldbach(n) == False:      # 如果任何一次测试返回False，则此猜想被推翻。
        print("Goldbach's Conjectur is False on ", n)
        break

4  =  2  +  2
6  =  3  +  3
8  =  3  +  5
10  =  3  +  7
12  =  5  +  7
14  =  3  +  11
16  =  3  +  13
18  =  5  +  13
20  =  3  +  17
22  =  3  +  19
24  =  5  +  19
26  =  3  +  23
28  =  5  +  23
30  =  7  +  23
32  =  3  +  29
34  =  3  +  31
36  =  5  +  31
38  =  7  +  31
40  =  3  +  37
42  =  5  +  37
44  =  3  +  41
46  =  3  +  43
48  =  5  +  43
50  =  3  +  47
>>>

这个实验证明，对于50以内的全部偶数，猜想都是成立的。你可以试着把验证区间调得大些，但我很有把握地告诉大家，在计算机可以表达的数值范围内，那个print函数从来都执行不到。

思考题：

• 为什么isprime()函数里，i循环到根号n就可以了？为什么不一直循环到n？
• 为什么goldbach()函数里，i循环到n/2就可以了？为什么不一直循环到n？