【Python】15.烟霏

天明独去无道路，

出入高下穷烟霏。

——韩愈《三石》

本期文章9040字

根据之前文章的后台统计数据推算

本期预计所需阅读时间51分钟

本系列文章已加入“维权骑士”(rightknights.com)的版权保护计划

本文原创内容受到保护

本期部分测试题思路较难

建议做题的时候使用演算纸整理思路

recursion（递归）

递归是函数式编程中一个非常重要的概念。

递归的基本思想是“自引用”——函数在内部调用自身（“自己调用自己”）。 递归主要用于解决那种可以分解为相同类型的更容易的子问题的问题。

以递归方式实现功能的函数的一个典型实例是阶乘函数。阶乘函数用于计算小于等于指定数字的所有正整数的乘积。

例如，

5!（5的阶乘） == 5 * 4 * 3 * 2 * 1 == 120

如果要用递归的方式执行此操作，我们需要考虑到：

5! == 5 * 4!

4! == 4 * 3!

3!== 3 * 2!

以此类推。一般来说，n! = n * (n - 1) !

此外，由于1是最小的正整数，所以1!不可再继续拆分，这种情况被称为基本情况，因为它需要在不继续进行拆分的情况下进行计算。

下面是阶乘函数的递归式实现。同时，我们输出了5!的值。

deffactorial(x):

if x == 1:

return 1

else:

return x *factorial(x-1)

print(factorial(5))

运行结果：

可以看到，基本情况相当于递归的退出条件。

测试题15.1.

选择，递归函数的基本情况是指？

永远不会发生的情况

涉及1的情况

不涉及对该函数的任何进一步调用的情况

点击下方空白区域查看答案

▼

不涉及对该函数的任何进一步调用的情况

也就是上文所说的“不继续进行拆分的情况下进行计算的情况”。

接下来，我们需要理解刚才递归函数的实现具体过程，这很重要，请务必亲自推导一遍并确保理解，否则后续文章部分内容可能会有很大的理解障碍。

我们把刚才的示例原样再放在这里，方便对照：

deffactorial(x):

if x == 1:

return 1

else:

return x *factorial(x-1)

print(factorial(5))

运行结果：

下面是运行过程分析：

①5作为参数传入最外层函数。

②5 != 1，进入else语句，执行return x *factorial(x-1)。5 - 1 == 4，4作为参数传给下一层函数。

③4 != 1，进入else语句，执行return x *factorial(x-1)。4 - 1 == 3，3作为参数传给下一层函数。

④3 != 1，进入else语句，执行return x *factorial(x-1)。3 - 1 == 2，2作为参数传给下一层函数。

⑤2 != 1，进入else语句，执行return x *factorial(x-1)。2 - 1 == 1，1作为参数传给下一层函数。

⑥1 == 1，进入if语句，执行return 1。1作为返回值返回⑤层的调用处。

⑦1参与到⑤层的return语句，⑤层处x == 2，故return语句返回值为2 * 1 == 2。2作为返回值返回④层的调用处。

⑧2参与到④层的return语句，④层处x == 3，故return语句返回值为3 * 2 == 6。6作为返回值返回③层的调用处。

⑨6参与到③层的return语句，③层处x == 4，故return语句返回值为4 * 6 == 24。24作为返回值返回②层的调用处。

⑩24参与到②层的return语句，②层处x == 5，故return语句返回值为5 * 24 == 120。120作为返回值返回最原始的调用处，即print函数内部得到的最终返回值为120，输出。

运行过程图解

递归函数是存在无限运行的情况的，就像无限循环一样。当我们没有设计基本情况的时候，通常会发生递归无限运行下去情况。

下面是阶乘函数的错误版本。这个阶乘函数没有基本情况，因此会一直运行下去，直到解释器耗尽内存并导致程序崩溃。

deffactorial(x):

return x *factorial(x-1)

print(factorial(5))

运行结果：

>>>

RuntimeError: maximum recursion depth exceeded

>>>

测试题15.2.

代码的输出结果是？

def sum_to(x):

return x + sum_to(x-1)

print (sum_to(5))

点击下方空白区域查看答案

▼

RuntimeError

这是求取小于等于给定参数的所有整数的和的函数，但是由于没有设计基本情况，导致函数永远自调用，无法停止。

测试题15.3.

设计代码。要求代码中包含一个函数，这个函数使用递归方式求取小于等于给定参数并且大于等于-10的所有正整数的和。另外，要求利用此函数得到[-10, 5]范围内所有整数的和，并使用print函数输出。

点击下方空白区域查看答案

▼

答案不唯一。参考答案如下：

def sum_to(x):

if x == -10:

return -10

else:

return x + sum_to(x-1)

print (sum_to(5))

递归也可以是间接的，就是说，一个函数可以“间接地”调用自己。实现方法一般为：一个函数调用第二个函数，这个第二个函数调用了第一个函数，然后在第一个函数中又调用第二个函数，依此类推。当然，三个及以上的函数也可以按这种方式循环调用。来看例子：

defis_even(x):

if x == 0:

return True

else:

returnis_odd(x-1)

defis_odd(x):

return notis_even(x)

print(is_odd(17))

print(is_even(23))

测试题15.4.

上面例子的运行结果是？

点击下方空白区域查看答案

▼

True

False

测试题15.5.难

代码的输出结果是？

def fib(x):

if x == 0 or x == 1:

return 1

else:

return fib(x-1) + fib(x-2)

print(fib(4))

点击下方空白区域查看答案

▼

5

经实际编写程序验证，5是正确答案。如果你得到的答案不是5，建议重新检查推导过程哪里出现了错误。

集合 set()

集合是另外一种数据结构，类似于数组和字典。

集合是使用花括号 { }或set函数创建的。

集合与数组之间有一些功能是相似的，例如都可以使用in来检查是否包含某个特定元素项。

num_set =

word_set = set(["spam", "eggs", "sausage"])

print(3innum_set)

print("spam" notinword_set)

运行结果：

>>>

True

False

>>>

要注意的是，如果需要创建空集，必须使用set()，因为空的花括号{ }创建的是一个空字典，而不是空集。同样，在输出时，Python解释器也使用set()在输出内容中表示空集。

测试题15.6.

代码的输出结果是？

letters = {"a", "b", "c", "d"}

if "e" not in letters:

print(1)

else:

print(2)

点击下方空白区域查看答案

▼

1

集合在几个方面与数组不同，但与数组有多个相同操作（如len）。集合与数组的不同之处主要在于：

集合是无序的，这意味着它们没有索引值。

集合不能包含重复元素。如果有重复元素，则只保留相同元素中的第一个。

在部分情况下，集合中元素被自动重新排序。

集合的存储方式决定了在使用in检查某一项是否是集合的一部分的时候，比使用in检查某一项是否是数组的一部分要更快。

如果要把元素添加到集合中，我们不使用数组中的append，而是使用add。

我们可以调用remove方法来从集合中删除特定元素，调用pop方法来删除集合中第一个元素。由于集合是无序的，在官方文档中，对这部分的描述为“pop方法删除的是任意一个元素”，但是经过实验，pop方法总是删除集合中第一个元素。

nums =

#除了第一个1，后面的相同元素都被自动抹去

#集合中元素被自动重新排序

print(nums)

nums.add(-7)

nums.remove(3)

print(nums)

print("下面是pop方法的示例")

while len(nums) > 0:

nums.pop()

print(nums)

运行结果：

下面是pop方法的示例

{-7}

set()

另外，被pop的元素可以在pop的同时以赋值给变量的方式备份下来，但被remove的元素无法在remove的同时赋值给变量进行备份。

nums =

print(nums)

a = nums.pop()

print(a)

b = nums.pop()

print(b)

print(nums)

c = nums.remove(6)

print(c)

运行结果：

1

2

None

可以看到，变量c为空值None，说明remove方法没有向c返回可以赋予的值。

测试题15.7.

填空，以创建一个集合。为这个集合添加字母“z”，并输出其长度（元素个数）。

nums = _____ "a", "b", "c", "d" _____

nums. _____ ("z")

print( _____ (nums))