有人可以解釋這種遞歸的工作原理嗎？

Question

我無法弄清楚它是如何工作的。

def exp(x,n): 
    if n == 0: 
     return 1 
    else: 
     return x * exp(x, n-1) 

print(exp(2, 4)) 

答案是16

Answer 1

exp(2, 4) = 2 * exp(2, 3) 
      = 2 * (2 * exp(2, 2)) 
      = 2 * (2 * (2 * exp(2, 1))) 
      = 2 * (2 * (2 * (2 * exp(2, 0)))) 
      = 2 * (2 * (2 * (2 * 1))) 

Answer 2

還原手：

? print(exp(2, 4)) 
! calculate(exp(2,4)) and print the result 
? exp(2,4) matches the definition: 
    exp(x,n) with x=2, n=4 
! substitute the variables in the function's body: 
    if 4==0: return 1 
    else: return 2 * exp(2, 4-1) 
! 4==0 is false 
? 2 * exp(2, 3) 
......... 
    2 * (2 * exp(2, 2)) 
......... 
    2 * (2 * (2 * exp(2, 1))) 

就可以完成的順序？