关于python:Python函数式编程系列004递归

从递推说起

说到代码复用，最低档次的代码复用就是基于 for/while 等的递推 (iteration) 思路了，它们的策略在代码行的反复，咱们能够看一下上面求幂的例子（这个例子将在之后会以各种面目呈现）：

def power1(x: float, n: int) -> float:
    res = 1
    for i in range(n):
        res *= x
    return res

这个例子不能全然地用纯函数的形式实现，因为如果咱们打印出 i 和res的取值，会发现 i 和res的都始终在变动。不过，单就从实现一个函数而言，其实 i 和res都是局部变量，咱们很大地限度了变量在函数外发挥作用。其实这种形式地应用「可变值」或者「副作用」的形式，咱们在前面探讨「不纯地函数式」中也会答应这种事件的产生。

然而，如果 res 和i不止呈现在了这么一个小范畴的函数里，而是整个大的模块代码块中，那么 i 和res的副作用就不容忽视了。

递归

回到这一篇的主题，如果单纯只用到函数的概念而没有环境的概念，咱们就须要下一个水管形态了，一个自援用的循环，相似一个带环的水管。当然这个水管不能是没有进口和没有入口的莫比乌斯。

stateDiagram-v2

    parameter --> function
    function --> function
    function --> [*]

咱们把这种函数自我援用称为递归(recursion)。当然，递归并不意味着没有副作用，甚至递归和函数式编程也没有必然的关联，过程式中仍旧能够应用递归。然而如果纯函数式编程，如果要想实现相似循环 / 复用的概念，递归是一个最根本的操作（前面也会介绍其余品种的循环的概念）。

下面求幂的函数，咱们能够很简略地实现为：

def power2(x: float, n: int) -> float:
    if n == 0:
        return 1
    else:
        return x * power2(x, n - 1)

尾递归

讲到递归，咱们可能就要提到递归的第一种优化计划，即尾递归的办法。递归在执行上速度十分不能让人称心的就是，诸如下面的幂运算中，要到最初算到 power2(x, 1) 的时候能力真的产生运算，之前都是在做表达式开展（或者说堆栈）的工作。譬如，对于计算 power2(2.0, 5) 时，经验了如下开展和计算的操作：

power2(2.0, 5)
2.0 * power2(2.0, 4)
2.0 * (2.0 * power2(2.0, 3))
2.0 * (2.0 * (2.0 * power2(2.0, 2)))
2.0 * (2.0 * (2.0 * (2.0 * power2(2.0, 1))))
2.0 * (2.0 * (2.0 * (2.0 * (2.0 * power2(2.0, 0)))))
2.0 * (2.0 * (2.0 * (2.0 * (2.0 * 1.0))))
2.0 * (2.0 * (2.0 * (2.0 * 2.0)))
2.0 * (2.0 * (2.0 * 4.0))
2.0 * (2.0 * 8.0)
2.0 * 16.0
32.0

一个解决方案就是让它立刻求值，这个对于求值优先而不是开展优先的语言来说（提速了堆栈的局部工夫），就能提速很多。此时咱们须要一个保留长期值的量，来保留即时计算的后果，如下：

def power3(x: float, n: int, acc: float = 1.0) -> float:
    if n == 0:
        return acc
    else:
        return power3(x, n - 1, acc * x)

对于一个优先求值的编译器来说，它的计算程序如下：

power3(2.0, 5, 1)
power3(2.0, 4, 1 * 2.0)
power3(2.0, 4, 2.0)
power3(2.0, 3, 2.0 * 2.0)
power3(2.0, 3, 4.0)
power3(2.0, 2, 4.0 * 2.0)
power3(2.0, 2, 8.0)
power3(2.0, 1, 8.0 * 2.0)
power3(2.0, 1, 16.0)
power3(2.0, 0, 16.0 * 2.0)
power3(2.0, 0, 32.0)
32.0

很遗憾的是，在 CPython 中，这个还是会有堆栈问题，PyPy则是欢送这种尾递归的优化。你能够通过第三方模块实现这个尾递归的操作。也有博客 (https://towardsdatascience.com/python-stack-frames-and-tail-call-optimization-4d0ea55b0542) 提供了本人的一个润饰器的实现。

import inspect

def tail_rec(func):
    rec_flag = False
    targs = []
    tkwargs = []
    def helper(*args, **kwargs):
        nonlocal rec_flag
        nonlocal targs
        nonlocal tkwargs
        f = inspect.currentframe()

        if  f.f_code == f.f_back.f_back.f_code:
            rec_flag = True
            targs = args
            tkwargs = kwargs
            return
        else:
            while True:
                try:
                    result = func(*args, **kwargs)
                except TypeError as e:
                    raise Exception("It is possible that the decorated function is not tail recursive")
                if rec_flag:
                    rec_flag = False
                    args = targs
                    kwargs = tkwargs
                else:
                    return result
    return helper

这样，咱们下面的幂函数就能够这个润饰器来达到无栈的尾递归版本：

@tail_rec
def power4(x: float, n: int, acc: float = 1.0):
    if n == 0:
        return acc
    else:
        return power4(x, n - 1, acc * x)

当然，有时为了掩藏这个 acc 的参数不要用户调用，咱们也能够应用高阶函数的办法，把它包裹起来，这样，acc就有点相似公有属性一样被暗藏起来，避免使用者谬误或者误会如何应用了。

@tail_rec
def power5(x: float, n: int):
    def helper(x: float, n: int, acc: float):
        if n == 0:
            return acc
        else:
            return helper(x, n - 1, acc * x)
    return helper(x, n, 1.0)

应用时即像 power1 一样调用就能够了，这样咱们就发现了函数作为返回值的另一个益处（掩藏公有变量）了：

>>> power5(2.0, 5)
32.0

附：其余优化计划

咱们在之后的润饰器和缓冲的内容中，将会介绍如何记忆后果缩小反复计算的办法。

结语

这篇文章之中，咱们学到了多元函数、作为参数的函数、作为返回值的函数之外的第四种水管，一个自我援用的环形水管，用此来在函数式的范畴内解决了须要代码服用 / 循环这一问题。