HOWTO · Python
Python 中的递归乘法
在 Python 中使用递归将两个整数相乘
本页内容
Python 已经可以用 * 进行整数乘法,但用递归编写乘法有助于理解如何把问题化为更小的同类问题。下面的示例涵盖重复加法、折半策略和基于累加器的变体。这些示例用于学习;在普通应用代码中,请使用内置运算符。
理解递归
递归函数通过使用较小的输入调用自身来解决问题。它需要一个基本情况:无需再次调用就能返回结果;还需要一个递归情况:让输入不断向基本情况推进。每次调用都会等待其子调用返回,然后随着调用逐层返回,尚未完成的操作也会依次完成。
对于通过重复加法实现的乘法,递归情况会让乘数减一,并把被乘数加到返回的结果上。当乘数为零时,就到达基本情况。如果没有一个最终能停止调用的条件,函数就无法产生结果。
基本递归乘法
最直接的写法是在每次调用时将第二个输入减一,然后在调用逐层返回时加上第一个输入。
运行此示例:
本节中的代码以及显示的标签或输出仍为英文。
def recursive_multiply(a, b):
if b == 0:
return 0
if b < 0:
return recursive_multiply(-a, -b)
return a + recursive_multiply(a, b - 1)
print(recursive_multiply(5, 3))
对于 b 的每个正整数单位,函数都会加一次 a。当 b 为负数时,同时改变两个数的符号,就能使用相同的正向计数递归,同时保持乘积不变;这种写法也支持负的被乘数。
每次调用都会将 b 减一,直到到达基本情况。随后调用按相反顺序返回,每一步都加上 a。这种递推关系容易理解,但调用次数与乘数的绝对值成正比。因此,乘数很大时可能会超过 Python 的递归限制。
处理负整数和零
同一个函数可以处理零以及所有符号组合。当乘数为零时,函数会立即返回零。对于负乘数,同时改变两个操作数的符号,就能将计算转换为正乘数的情况,并保持数学乘积不变。
本节中的代码以及显示的标签或输出仍为英文。
def recursive_multiply(a, b):
if b == 0:
return 0
if b < 0:
return recursive_multiply(-a, -b)
return a + recursive_multiply(a, b - 1)
for pair in ((5, 3), (-5, 3), (5, -3), (-5, -3), (5, 0)):
print(pair, recursive_multiply(*pair))
四种非零符号组合的结果遵循通常的符号规则:两个操作数同号,结果为正;异号,结果为负。只要有一个操作数为零,结果就是零。循环会在每一对输入旁打印其乘积,便于比较符号变化对结果的影响。
通过折半减少递归调用
当乘数可以折半时,就不必反复减一。对于正数 b,令 half 为 a 与 b // 2 的乘积。如果 b 是偶数,完整结果就是 half + half;如果是奇数,还需要再加一个 a。使用整数除法和余数判断即可表示这个递推过程,无需使用位运算。
本节中的代码以及显示的标签或输出仍为英文。
def multiply_by_halving(a, b):
if b == 0:
return 0
if b < 0:
return multiply_by_halving(-a, -b)
half = multiply_by_halving(a, b // 2)
if b % 2 == 0:
return half + half
return half + half + a
print(multiply_by_halving(5, 3))
每一步递归都会将乘数大致减半,因此调用深度取决于乘数可以被折半多少次,而非乘数本身的大小。这个方法仍然会进行加法,也仍然使用 Python 的调用栈。它有助于说明如何简化递推关系,不过在普通代码中,直接使用内置乘法更简单。
Python 中的尾递归
在尾递归函数中,递归调用是最后一步操作;累加器会在调用过程中保存并传递结果。这改变了未完成工作的记录方式,但 Python 不会通过复用同一个栈帧来优化尾调用,因此调用栈的限制依然存在。
本节中的代码以及显示的标签或输出仍为英文。
def tail_recursive_multiply(a, b, accumulator=0):
if b == 0:
return accumulator
if b < 0:
return tail_recursive_multiply(-a, -b, accumulator)
return tail_recursive_multiply(a, b - 1, accumulator + a)
print(tail_recursive_multiply(5, 3))
累加器从零开始,每向前递归一步就增加一个 a。乘数达到零时,累加器中保存的就是乘积。与重复加法一样,这个版本的调用次数与乘数的绝对值成正比,因此使用尾调用风格并不能让 Python 安全处理很大的输入。
递归乘法适用于什么情况
这些实现展示了基本情况、递归如何推进,以及线性和对数级调用深度之间的区别。重复加法和尾递归版本的调用深度是线性的;折半版本的调用深度是对数级的。所有这些方法仍有函数调用和调用栈开销,而且 Python 不保证不同环境中存在固定的递归深度阈值。
对于实际的整数运算,优先使用 a * b:写法更清晰,也能避免额外的 Python 层递归调用。学习递归,或题目明确要求使用递归形式时,可以使用递归乘法;同时要确保输入规模适合所选的递推方式。