递归函数

递归（Recursion），又译为递回，在数学与计算机科学中，是指在函数的定义中使用函数自身的方法。

下面通过两个最典型的例子来了解什么是递归。

计算阶乘n! = 1 * 2 * 3 * ... * n，可以直到只有当n=1时需要特殊处理，因此我们写出以下计算阶乘的函数：

def func1(n):
    if n == 1:
        return 1
    return n * func(n-1)

计算斐波那契数列

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

递归函数的优点是定义简单，逻辑清晰。理论上，所有递归函数都可以用循环的方式实现，但循环的逻辑表现出来可能比较繁琐且复杂。以上的两个例子都还可以再优化，这个涉及到栈溢出以及重复计算，可以使用尾递归和记忆法来优化以上问题。这里不做详细的介绍。后续会有专门的递归专辑来讲解。

高阶函数

高阶函数（Higher-order function），下面通过几个例子逐步深入了解。

函数赋值给变量（即变量指向函数）

Python内置函数min()，我们可以在窗口直接输入min：

>>> min
<built-in function min>

从上面的输出中可以直到，min()函数是Python的内置函数。下面用它来求最小值：

>>> min(6,1)
1

我们可以把函数的结果赋值给变量：

>>> m = min(6,1)
>>> m
1

以上我们可以直到，min是函数本身，min(6,1)是函数的调用。那么如果将函数本身赋值给变量会怎样呢？

>>> m = min
>>> m
<built-in function min>
>>> m(6,1)
1

由上面的结果可以看出，函数本身可以赋值给变量，该变量指向了函数，且可以通过该变量来调用此函数。

函数名即变量

每个函数都有一个名字，那函数名又是什么呢？其实函数名实际上就是指向该函数的变量。对于min()这个函数，其实可以把函数名min看成变量，而这个变量实际上指向的是一个可以计算最小值的函数。那么，如果我们把这个变量min指向其他对象会怎样呢？

>>> min = 24
>>> min
24
>>> min(6,1)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'int' object is not callable

可以看到min指向24后，min这个变量就指向了整数24而不再指向求最小值的函数，当然虽然代码上这样是可行的，不过这里只是为了说明函数名也是变量，实际应用中切不可这样操作。若想要恢复min函数，可以重启Python交互环境。
Tips：由于min函数实际上是定义在import builtins模块中，所以要让修改min变量的指向在其他模块中也生效，要用import builtins; builtins.min = 10。

作为参数传入函数

上面了解到变量可以指向函数，而函数的参数可以接收变量，那么一个函数就可以接收另一个函数作为参数，即函数可以作为参数传入另一个函数，这种函数就称之为高阶函数。下面来看个例子：

def add_abs(a,b,f):
    return f(a) + f(b)

我们给上面定义的函数传入这样的参数add_abs(-2,6,abs)：

>>> def add_abs(a,b,f):
...  return f(a)+f(b)
... 
>>> 
>>> add_abs(-2,6,abs)
8

根据函数的定义，我们直到参数a，b，f 分别接收 -2，6，abs，然后在函数内部分别求a，b的绝对值再相加作为结果返回。

下面开始介绍一些高阶的函数

map()函数

map()函数接收两个参数，一个是函数，一个是Iterable，map将传入的函数依次作用到序列的每个元素，并把结果作为新的Iterable返回。例如现有一个函数f(x) = x^2，要把这个函数作用在一个list[1,2,3,4,5,6,7,8,9]上，就可以用map()实现如下：

>>> def f(x):
...  return x * x
... 
>>> res = map(f,[1,2,3,4,5,6,7,8,9])
>>> list(res)
[1, 4, 9, 16, 25, 36, 49, 64, 81]

map()传入的第一个参数是f，即函数对象本身。由于结果res是一个Iterable，Iterabe是惰性序列，因此通过list()函数让它把整个序列都计算出来并返回一个list。
我们还可以将这个list中的所有数字转为字符串：

>>> res = map(str,[1,2,3,4,5,6,7,8,9])
>>> list(res)
['1', '2', '3', '4', '5', '6', '7', '8', '9']
>>> 

reduce()函数

reduce把一个函数作用在一个序列[x1,x2,x3,...]上，这个函数必须接受两个参数，reduce把结果继续和序列的下一个元素做累积计算，其效果就是：

reduce(f,[x1,x2,x3,x4]) = f(f(f(x1,x2),x3),x4)

比方说对一个序列求和，就可以用reduce实现：

>>> from functools import reduce
>>> def add(x,y):
...  return x + y
...
>>> reduce(add,[1,3,5,7,9])
25

当然和运算可以直接用Python内建函数sum()，没必要动用reduce。

但是如果要把序列[1,3,5,7,9]变换成整数13579，reduce就可以派上用场：

>>> def fn(x,y):
...  return x * 10 + y
...
>>> reduce(fn,[1,3,5,7,9])
13579

这个例子本身没多大用处，但是，如果考虑到字符串str也是一个序列，对上面的例子稍加改动，配对map()，我们就可以写出把str转换为int的函数：

>>> def fn(x,y):
...  return x * 10 + y
...
>>> def char2num(s):
...  digits = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
...  return digits[s]
...
>>> reduce(fn,map(char2num,'13579'))
13579

整理成一个str2int的函数就是：

from functools import reduce
DIGITS = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
def str2int(s):
	def fn(x,y):
		return x * 10 + y
	def char2num(s):
		return DIGITS[s]
	return reduce(fn,map(char2num,s))

还可以用lambda函数进一步简化：

from functools import reduce
DIGITS = {'0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6, '7': 7, '8': 8, '9': 9}
def char2num(s):
	return DIGITS[s]

def str2int(s):
    return reduce(lambda x,y:x * 10 + y, map(char2num, s))

也就是说，假设Python没有提供int()函数，你完全可以自己写一个把字符串转转化为整数的函数，而且只需要几行代码！

filter函数

Python内建的filter()函数用于过滤序列。
和map类似，filter()也接收一个函数和一个序列。和map()不同的是，filter()把传入的函数依次于每个元素，然后根据返回值是True还是False决定保留还是丢弃该元素。
例如，在一个list中，删掉偶数，只保留奇数，可以这么写：

def is_odd(n):
    return n%2 == 1

result = filter(is_odd,[1,2,3,4,5,6,7,8,9,10])
print(type(result))
list(result)

<class ‘filter’>
[1, 3, 5, 7, 9]

把一个序列中的空字符串删除掉，可以这么写：

def not_empty(s):
    return s and s.strip()

list(filter(not_empty,['A','b','',None,'O','']))

[‘A’, ‘b’, ‘O’]

可见用filter()这个高阶函数，关键在于正确实现一个“筛选”函数。
注意到filter()函数返回的是一个Iterator，也就是一个惰性序列，所以要强迫filter()完成计算结果，需要用list()函数获得所有结果并返回list。

用filter求素数

计算素数的一个方法是埃氏筛法，它的算法理解起来非常简单：
首先，列出从2开始的所有自然数，构造一个序列：
2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,...
取序列的第一个数2，它一定是素数，然后用2把序列的2的倍数筛掉：

取序列的第一个数3，它一定是素数，然后用3把序列的3的倍数筛掉：

取序列的第一个数5，然后用5把序列的5的倍数筛掉“

不断筛下去，就可以得到所有的素数。
用Python来实现这个算法，可以先构造一个从3开始的奇数序列：

def _odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n

注意这是一个生成器，并且是一个无限序列。
然后定义一个筛选函数：

def _not_divisible(n):
    return lambda x:x % n > 0

最后，定义一个生成器，不断返回下一个素数：

def primes():
    yield 2
    it = _odd_iter()      # 初始序列
    while True:
        n = next(it)      # 返回序列的第一个数
        yield n
        it = filter(_not_divisible(n),it)

这个生成器返回第一个素数2，然后，利用filter()不断产生筛选后的新的序列。
注意，由于primes()也是一个无限序列，所以调用时需要设置一个退出循环的条件：

# 调用
# 打印1000以内的素数
for n in primes():
    if n < 1000:
        print(n)
    else:
        break

注意到Iterator是惰性计算的序列，所以我们可以用Python表示”全体自然数“、”全体素数“这个的序列，而代码非常简介。

sorted函数

Python内置的sorted()函数可以对list进行排序：

sorted([5,8,-6,35,-24,10])
# [-24, -6, 5, 8, 10, 35]

此外，sorted()函数也是一个高阶函数，它还可以接收一个key函数来实现自定义的排序，例如按绝对值大小排序：

sorted([5,8,-6,35,-24,10],key=abs)
# [5, -6, 8, 10, -24, 35]

再看看字符串排序的例子：

sorted(['Amy','bob','John','Alex','Zoom','aodi','cry'])
# ['Alex', 'Amy', 'John', 'Zoom', 'aodi', 'bob', 'cry']

默认情况下，对字符串排序，是按照ASCII的大小比较的，由于'z' < 'a'，结果，大写字母会排在小写字母a的前面。
现在，我们提出排序应该忽略大小写，按照字母序排序。要实现这个算法，不必对现有代码大加改动，只要我们能用一个key函数把字符串映射为忽略大小写排序即可。忽略大小写来比较两格字符串，实际上就是先把字符串都变成大写（或者变成小写），再比较。这样，我们给sorted传入key函数，即可实现忽略大小写的排序：

sorted(['Amy','bob','John','Alex','Zoom','aodi','cry'],key = str.lower)
# ['Alex', 'Amy', 'aodi', 'bob', 'cry', 'John', 'Zoom']

要进行反向排序，不必改动key函数，可以传入第三个参数reverse=True：

sorted(['Amy','bob','John','Alex','Zoom','aodi','cry'],key = str.lower,reverse=True)
# ['Zoom', 'John', 'cry', 'bob', 'aodi', 'Amy', 'Alex']

从上述例子可以看出，高阶函数的抽象能力是非常强大的，而且，核心代码可以保持得非常简介。