我可以用递归替换幂运算符（**）吗？

Question

在函数定义过程中应用递归原理可以降低编码的难度，提高编码的趣味性。你知道吗

例如，我有一个简单的函数来求一个特定数字的幂：

def power(a, b):
   return a**b

但是如果我决定不使用**，在这种情况下，我想应用递归原理。你知道吗

我想在块范围内调用相同的函数。 我试过这个：

def power (a, b) :
   return a*power(a, b-1)

打印时输出错误消息

print power(3,3) 

Runtime Error: maximum recursion depth  exceeded 

导致此错误的原因是什么？如何改进代码？你知道吗

Answer 1

注释的汇编示例：

def power(a, b):
    if b == 0:
        return 1
    return a * power(a, b - 1)

递归需要一个基本情况——它告诉程序“嘿，这是你应该做的。开始退货吧！”你知道吗

Edit：无论如何，递归不能保证在Python中得到很好的实现。语言规范没有断言如何处理递归，这意味着深度递归将溢出堆栈。（这与其他语言不同，例如大多数函数式编程语言，其中递归更优化。）在我的计算机上，使用CPython：

>>> def power(a, b):
...     if b == 0:
...         return 1
...     return a * power(a, b - 1)
>>>
>>> power(1, 10)
1
>>> power(1, 981)
1
>>> power(1, 982)
Traceback (most recent call last):
  File "<input>", line 1, in <module>
    power(1, 982)
  File "<input>", line 4, in power
    return a * power(a, b - 1)
  File "<input>", line 4, in power
    return a * power(a, b - 1)
  File "<input>", line 4, in power
    return a * power(a, b - 1)
  [Previous line repeated 978 more times]
  File "<input>", line 2, in power
    if b == 0:
RecursionError: maximum recursion depth exceeded in comparison

此外，CPU可能比常规乘法更有效地执行指数运算，因此递归编写此函数可能比使用内置运算符慢。你知道吗

Answer 2

你可以利用“分而治之”的策略，既可以提高速度，也可以在不破坏堆栈的情况下计算非常大的功率。下面的关系和实现都假定幂参数为非负整数值。你知道吗

你已经注意到了a**b == a * a**(b-1)。然而，当b是偶数时a**b == (a*a)**(b/2)也是正确的，这将问题大小减少一半而不是减少1。与递归一样，还需要基本情况a**0 == 1。综合起来，我们得到：

def power(a, b):
    if b == 0:
        return 1
    result = power(a * a, b // 2)           # calculate the halved problem
    return a * result if b & 1 else result  # and multiply by a if b is odd

它允许我们计算power(2, 2000)：

你知道吗114813069527425452423283320117768198402231770208869520047764273682576626139237031385665948631650626991844596463898746277344711896086305533142593135616665318539129989145312280000688779148240044871428926990063486244781615463646388363947317026040466353970904996558162398808944629605623311649536164221970332681344168908984458505602379484807914058900934776500429002716706625830522008132236281291761267883317206598995396418127021779858404042159853183251540889433902091920554957783589672039160081957216630582755380425583726015528348786419432054508915275783882625175435528800822842770817965453762184851149029376. 你知道吗

对于b == 2000，该算法的递归堆栈增长为O（logb），与11成正比。你知道吗