Python递归实现无乘法操作的乘法函数工作原理咨询

嘿，我来帮你把这个递归乘法函数的逻辑掰碎了讲清楚，其实它核心是用了乘法分配律和二分简化的思路，咱们先把你的代码放出来：

a=int(input('Enter a '))
b=int(input('Enter b '))
def mult(a,b):
    if a==0 or b==0:
        return 0
    elif b%2==0:
        return 2*mult(a, b/2)
    else:
        return mult(a, b-1)+a
print('Result = ', mult(a,b))

先搞懂三个分支的作用 #

这个函数的递归逻辑是靠「逐步缩小问题规模」来实现的，每个分支对应不同的情况：

1. 基线条件（递归终止的开关）

if a==0 or b==0:
    return 0

这是最直观的：任何数乘0结果都是0，只要a或b有一个是0，递归就直接停止，返回0。

2. 当b是偶数时的逻辑

elif b%2==0:
    return 2*mult(a, b/2)

这里用了乘法的结合律：比如a*6可以拆成2*(a*3)，因为6是2的倍数。递归调用mult(a, b/2)就是把问题规模缩小一半——原来算a*b，现在只需要算a*(b/2)，再把结果翻倍就行。

3. 当b是奇数时的逻辑

else:
    return mult(a, b-1)+a

奇数可以拆成「偶数+1」，比如a*5 = a*(4+1) = a*4 +a。所以这里先递归计算a*(b-1)（b-1就变成偶数了，会走上面的分支），再加上一个a，就得到最终结果。

举个实际例子走一遍，你就懂了 #

假设输入a=3，b=5，咱们一步步追踪递归过程：

1. 调用mult(3,5)：b是奇数，返回mult(3,4) + 3
2. 调用mult(3,4)：b是偶数，返回2 * mult(3,2)
3. 调用mult(3,2)：b是偶数，返回2 * mult(3,1)
4. 调用mult(3,1)：b是奇数，返回mult(3,0) +3
5. 调用mult(3,0)：触发基线条件，返回0

现在开始往回计算结果：

• mult(3,1) = 0 +3 =3
• mult(3,2)=2*3=6
• mult(3,4)=2*6=12
• mult(3,5)=12+3=15（和3*5的结果一致）

回答你的两个疑问 #

1. 当数值不为0时该代码如何运行？
   只要初始a和b都不为0，函数会根据b的奇偶性，不断把问题拆成更小的子问题：要么把b减半（偶数时），要么把b减1变成偶数（奇数时），直到某个子问题触发「b=0」的基线条件。

2. 是否会递归至数值为0？
   一定会！不管你初始的b是奇数还是偶数，最终都会递归到b=0的情况：

   • 如果b是偶数，不断减半后会变成1（比如6→3→1），1是奇数，减1就变成0；
   • 如果b是奇数，先减1变成偶数，再重复上面的过程，最终也会到0。

内容的提问来源于stack exchange，提问作者nameless