为什么函数调用的值和次数不同，这段代码中的递归是如何工作的？

Question

更新：我想知道这个类似代码的递归是怎么工作的？

def fib( n ):
    global cnt
    cnt += 1 #global cnt is assigned and changed
    if n <= 2:
        return 1
    return fib( n - 1 ) + fib( n - 2 )

cnt = 0
print(fib( 10 ))
print("fib is called", cnt, "times") #109 times!

旧问题：

def power_of_two(n):
    global cnt
    cnt += 1
    if n == 0:
        return 1
    return 2 * power_of_two(n-1)
cnt = 0
print(power_of_two(3))
print("power_of_two is called", cnt, "times")

问题：当上面的代码执行时，cnt的值是多少，函数power_of_two()被调用了多少次？

A. 8，调用4次
B. 4，调用3次
C. 6，调用4次
D. 3，调用3次

我运行了代码，结果显示cnt是4，所以应该是答案B吗？但是答案B说代码调用了3次，那不应该是4次吗？如果是3次，那是为什么呢？我也考虑过选择答案A，因为那听起来更合理，但它问的是cnt的值，而不是(power_of_two(3))的值。或者我误解了问题，还是我老师写的问题有误？我知道这是一个基础的编程问题，但非常感谢你的帮助 :)

Answer 1

对于 n=3 的情况，总共会有 4 次步骤来执行你的代码。

当 n==3 时，你的 cnt ==1，这时会返回 2*，这是递归的第一步。

当 n==2 时，cnt ==2，这时会返回 2*2*，这是递归的第二步。

当 n==1 时，cnt==3，这时会返回 2*2*2*，这是递归的第三步。

最后一步是通过 if n==0 来停止递归，这时 cnt==4，会返回 2*2*2*1，这是递归的第四步。

最终结果是 A) 8，总共 4 次