Python函数式编程系列004（递归） python递归函数式编程

从递推说起说到代码复用，最低层次的代码复用就是基于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-v2parameter --> 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 inspectdef tail_rec(func): rec_flag = False targs = [] tkwargs = [] def helper(*args, **kwargs): nonlocal rec_flag nonlocal targs nonlocal tkwargs f = inspect.currentframe()iff.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

附：其他优化方案
我们在之后的修饰器和缓冲的内容中，将会介绍如何记忆结果减少重复计算的方法。
结语 【Python函数式编程系列004（递归）】这篇文章之中，我们学到了多元函数、作为参数的函数、作为返回值的函数之外的第四种水管，一个自我引用的环形水管，用此来在函数式的范围内解决了需要代码服用/循环这一问题。