Python递归函数逻辑疑问：幂运算递归函数执行原理解析

先看你写的递归函数代码：

def powertoK(k, s): 
    if s != 0:
        return k* powertoK(k,s-1)
    else:
        return 1
powertoK(3, 7) 

你的疑问：

我无法理解该函数的工作原理：其基准条件为当s变为0时返回1，但为何最终返回值实际为k^{s而非始终为1？是否存在两个分别存储1和k}s的内存地址？

函数工作原理拆解 #

拿powertoK(3,7)的执行过程举例：

• 最外层调用powertoK(3,7)，此时s=7≠0，需要计算3 * powertoK(3,6)，但powertoK(3,6)的结果还没出来，所以先暂停当前计算，去调用powertoK(3,6)
• 调用powertoK(3,6)，s=6≠0，同样需要计算3 * powertoK(3,5)，继续暂停并调用下一层
• 这个过程一直重复，直到调用powertoK(3,0)，此时触发基准条件，直接返回1
• 现在开始回溯计算：
  • powertoK(3,1)拿到powertoK(3,0)返回的1，计算3*1=3并返回
  • powertoK(3,2)拿到powertoK(3,1)返回的3，计算3*3=9并返回
  • 以此类推，每一层都把下一层的返回值和当前的k相乘，直到最外层powertoK(3,7)拿到powertoK(3,6)返回的729，计算3*729=2187（也就是3^7）后返回

关于内存的疑问 #

不存在两个固定存储1和k^s的内存地址。递归调用时，每一次函数调用都会在调用栈里生成一个独立的栈帧，每个栈帧里存储着当前调用的k、s参数，以及尚未完成的计算状态。当基准条件返回1后，这个值会被上一层的栈帧接收，完成乘法计算后再传给更上层的栈帧，直到最外层栈帧生成最终结果。所有栈帧在递归完成后都会被系统回收，不会一直占用内存。

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