Как получить общее количество фреймов стека, используемых в рекурсии в Python?

Question

здесь простой код для вычисления ряда Фибоначчи:

def fib(n): 
    if n==0 or n==1: 
     return 1 
    else: 
     return fib(n-1)+fib(n-2) 

, если п = 10, я хочу знать, сколько кадры стека задействованы для этого расчета. Есть ли способ получить в реальном времени?

Answer 1

Самое простое решение, чтобы добавить дополнительный параметр, затем пропустите его через результат:

def fib(n, depth=1): 
    if n == 0 or n == 1: 
     return (1, depth) 
    else: 
     result1, depth1 = fib(n-1, depth+1) 
     result2, depth2 = fib(n-2, depth+1) 
     return (result1 + result2, max(depth1, depth2)) 

Это вернет число Фибоначчи, сопряженное с глубиной рекурсии.

Тест:

>>> list(map(fib, range(5))) 
[(1, 1), (1, 1), (2, 2), (3, 3), (5, 4)] 

Answer 2

import inspect 
def fib(n): 
    fib.calls += 1 
    print "depth =", len(inspect.stack()) 
    print "calls =", fib.calls 
    if n == 0 or n == 1: 
     return 1 
    else: 
     return fib(n - 1) + fib(n - 2) 

например

>>> fib.calls = 0 
>>> fib(5) 
depth = 2 
calls = 1 
depth = 3 
calls = 2 
depth = 4 
calls = 3 
depth = 5 
calls = 4 
depth = 6 
calls = 5 
depth = 6 
calls = 6 
depth = 5 
calls = 7 
depth = 4 
calls = 8 
depth = 5 
calls = 9 
depth = 5 
calls = 10 
depth = 3 
calls = 11 
depth = 4 
calls = 12 
depth = 5 
calls = 13 
depth = 5 
calls = 14 
depth = 4 
calls = 15 
8