快速模幂算法递归调用处理机制及返回语句可达性疑问

递归调用的处理逻辑 #

快速模幂的核心是分治思想，通过把大指数的幂运算拆成更小的子问题递归解决：

• 当指数p为0时，直接返回1（这是递归的终止条件，所有递归最终都会走到这里）
• 若p是偶数：将a^p mod n拆解为(a^(p/2))² mod n，先递归计算a^(p/2) mod n得到t，再返回t² mod n
• 若p是奇数：将a^p mod n拆解为a * (a^((p-1)/2))² mod n，先递归计算a^((p-1)/2) mod n得到t，再返回a*(t² mod n) mod n

第二、第三条return语句的执行路径 #

这些return语句能被执行到，是因为递归调用是有去有回的：
每一层递归调用都会先把指数p缩小，直到触发p=0的终止条件并返回结果。之后这个结果会逐层回传给上层调用，上层拿到t后，就会执行后续的平方/乘法取模操作，最后执行return语句返回当前层的结果。

举个具体例子，计算a^5 mod n：

1. 初始调用p=5（奇数），递归调用p=(5-1)/2=2
2. p=2（偶数），递归调用p=2/2=1
3. p=1（奇数），递归调用p=(1-1)/2=0
4. p=0返回1，回到p=1的调用，得到t=1，执行a*(1² mod n) mod n后return这个结果
5. 回到p=2的调用，得到t是p=1的返回值，执行t² mod n后return
6. 回到初始调用p=5，得到t是p=2的返回值，执行a*(t² mod n) mod n后return

不会陷入递归循环的原因 #

每次递归调用的指数p都会严格减小：

• 若p是正偶数，p/2必然小于p
• 若p是正奇数，(p-1)/2也必然小于p（比如p=1时，(1-1)/2=0）
  最终p一定会降到0，触发终止条件返回，递归会逐层退出，不会无限循环。

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