Python 使用递归处理集合

Python 使用递归处理集合，也可以用递归的形式定义对集合的处理，例如用递归的形式定义map()函数，公式如下：

对空集合的映射结果仍然是一个空序列，对非空集合，则是由3部分组成的递归形式的表达式。首先将函数应用于除最后一个元素外的集合，形成一个新序列，然后对集合最后一个元素应用函数，最后将返回结果追加到之前生成的序列上。

先前的map()函数的纯递归实现如下：

from typing import Callable, Sequence, Any
def mapr(
        f: Callable[[Any], Any],
        collection: Sequence[Any]
    ) -> List[Any]:
    if len(collection) == 0: return []
    return mapr(f, collection[:-1]) + [f(collection[-1])]

map(f, [])的返回值是一个空列表对象，当输入值是非空列表时，首先将函数应用于列表的最后一个元素，然后将它追加到以递归形式定义的列表上，这个列表是函数应用于输入序列头部形成的。

需要说明的是，这里的mapr()函数返回一个列表对象，类似于Python 2中老版本的map()函数。Python 3的map()函数返回的是可迭代对象，而不是列表对象。

虽然这个实现很简洁，但没有尾调用优化。如果实现了尾调用优化，就能突破调用栈深度1000的限制，并大幅提升处理速度。

Callable[[Any], Any]是比较宽松的类型标示，用于定义领域类型变量和范围类型变量，后续的实例中会用到它。