Python 保持递归形式

Python 保持递归形式，有些情况下，递归形式的定义是最优解。一些递归实现通过分治策略极大地降低了工作量，例如通过平方法计算幂次函数，计算公式如下：

将整个计算过程划分为3种情况，用Python的递归形式实现如下：

def fastexp(a: float, n: int) -> float:
    if n == 0:
        return 1
    elif n % 2 == 1:
        return a * fastexp(a, n-1)
    else:
        t = fastexp(a, n // 2)
        return t * t

函数有3个分支。将基础型式fastexp(a, 0)的返回值定义为1，另外两个分支采用不同的处理策略，如果幂次为奇数，以递归形式定义返回值。幂次n减小1，属于简单的尾递归优化情形。

如果幂次为偶数，则使用n/2计算返回值，问题规模缩小为原来的一半。由于问题规模是折半缩小的，所以处理速度会明显提升。

这种函数无法简单地改为尾调用优化循环。由于递归形式已经是最优解，无须进一步优化了。Python的递归限制是 n \leq 2^{1000}，已经相当大了。

函数的类型标示表明参数类型为浮点数，并接收整型参数。根据Python的类型转换规则，当需要处理这两类数值时，使用浮点数作为函数类型标示更简单。