使用递归将基数从指数提高到指数

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

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

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

Answer 2

你的递归有点不对劲。由于 2 y = 2 * 2 y-1，因此有 x 2 y = x 2 * x^2y-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 3

答案已经在这里。

从@MalikBrahimi

def power(x, y):
    if y == 1:
        return x
    else:
        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 4

使用Malik Brahimi的答案，你可以写一个幂函数，然后让你的初始调用是power（x，power（2，y））。

Answer 5

这里和其他类似问题下的答案都没有考虑指数为负的情况。

这是一个可行的解决方案：

def power(base, exponent):
    if base == 0:
        if exponent == 0:
            return 1.0 # 0 ^ 0 is undefined. Using 1.
        else:
            return 0
        
    if exponent == 0:
        return 1
    dbl_power = base * power(base, abs(exponent) - 1)
    # if exponent is negative, take reciprocal
    if exponent < 0:
        dbl_power = 1 / dbl_power
    return dbl_power