python - 如何计算递归调用次数？

Question

如前所述。我通过递归编写斐波那契代码 -

def fib(n):
    x = 0
    if n == 0 or n == 1:
        return 1
    else:
        print('computing : ', n) # this show the recursive call.
        x = x +1
        print('recursive call no total : ',x) # this show the how many number of recursive call.
        return fib(n-1) + fib(n-2)

但是这个打印， 递归调用次数:1 递归调用次数:1 继续 1 。

出现一些问题。我想不通。 x 的值不会增加，因为它不是迭代过程。但是我如何通过每次递归调用来增加 x 的值？

使用全局变量，我尝试解决 ans 问题。代码可能如下所示-

def fib(n):
    global numcalls
    numcalls += 1 #this will increment with every fib() call
    if n ==0 or n ==1:
        return 1
    else:
        return fib(n-1) + fib(n-2)
    print('numcalls =', numcalls)

然后调用该函数， 调用次数 = 0 纤维蛋白(5)

上面的代码可以吗？如果没有，那么就提出一些有关错误的建议。

Answer 1

执行此操作的几种方法

我们可以使用计数器，就像您尝试的那样，稍作更改:

def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        print('computing : ', n)  # this show the recursive call.
        fib.x = fib.x + 1
        # this show the how many number of recursive call.
        print('recursive call no : ', fib.x)
        return fib(n - 1) + fib(n - 2)

fib.x = 0
fib(6)

我们还可以使用装饰，参见 Python: static variable decorator

这样做的一个副作用是，每次调用 fib 时，您都必须手动重置 fib.x = 0，在函数中处理此问题的一种方法是采用一个额外的参数，该参数将仅通过递归调用指定，不重置 fib.x = 0:

def fib(n, _from_user=True):
    if _from_user: #default was used so the call was from the user, set x to 0 now
        fib.x = 0
    if n == 0 or n == 1:
        return 1
    else:
        print('computing : ', n)  # this show the recursive call.
        fib.x = fib.x + 1
        # this show the how many number of recursive call.
        print('recursive call no : ', fib.x)
         #pass _from_user =  False for sub calls
        return fib(n - 1, False) + fib(n - 2, False)

fib(6)