使用递归将基提升为指数

Question

我正在尝试使用递归将基数提升为2的幂，然后将其提升为指数，所以它看起来像x^2^y。

这是我的代码：

def real_multiply(x:int, y:int):
    if y == 0:
        return x
    else:
        return x * real_multiply(x,(2**y)-1)

基本情况y==0是这样2^0返回1，最终输出是x^1，它将返回x。但是，当我运行这段代码时，它会达到递归限制。

有什么想法吗？

Answer 1

你的递归有点不对劲。因为2^y=2*2^y-1，所以x^{2y=x2*x2y-1。因此，递归应该是}

if y == 1:
    return x * x
else:
    # return x**2 * real_multiply(x, 2**(y-1))
    return x * 2 * real_multiply(x, real_multiply(2, y-1))

（在这里，我完全避免使用**。嵌套递归！）

Answer 2

答案已经在这里了。

来自@MalikBrahimi

def power(x, y):
    if y == 1:
        return x

    if y != 1:
        return x * power(x, y - 1)

来自@JacobMcCarthy

In [5]: x = 2

In [6]: y = 4

In [7]: power(x, power(2, y))
Out[7]: 65536

In [8]: x ** 2 ** y
Out[8]: 65536

OP可能会说，“不，我需要一个只接受x和y作为参数的函数。好的：

def super_power(x, y):
    return power(x, power(2, y))

Answer 3

我不明白你在递归中做什么，但这是一个典型的指数函数：

def power(x, y):
    if y == 1:
        return x

    if y != 1:
        return x * power(x, y - 1)