Как рассчитать количество рекурсивных вызовов?

Question

As ex. Я пишу fibonancci код рекурсией -

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.

theres возникли некоторые проблемы. Я не могу понять. Значение x не увеличивается, так как это не итеративные процессы. Но как я могу увеличить значение x через каждый рекурсивный вызов?

Используя глобальную переменную, я попытался решить проблему. Код может нравится

ценам ниже

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) 

Тогда вызов функции с, 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.x = 0 каждый раз, когда вы вызываете fib, один из способов обработки этого в функции - это принять дополнительный аргумент, который будет указан только рекурсивными вызовами, чтобы не сбрасывать 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) 

Answer 2

Используя глобальную переменную, я попытался решить проблему 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) 

Тогда вызов функции с, numcalls = 0 Фибо (5)

ли код выше нормально? Если нет, то предложите что-нибудь о ошибках.