1

here is the simple code for calculating fibonacci series:

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

if n=10, I want to know how many stack frames are involved for this calculation. Is there a way to get in real time?

brain storm
  • 30,124
  • 69
  • 225
  • 393
  • 1
    Maybe this can help: http://stackoverflow.com/questions/1156023/print-current-call-stack-in-python – kiasy Nov 11 '13 at 23:58

2 Answers2

3

The simplest solution is to add an extra parameter, then thread it through the result:

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))

This will return the Fibonacci number, paired with the recursion depth.

Test:

>>> list(map(fib, range(5)))
[(1, 1), (1, 1), (2, 2), (3, 3), (5, 4)]
Lambda Fairy
  • 13,814
  • 7
  • 42
  • 68
  • That's because I assumed you want the maximum recursion depth. If you want to count the number of calls instead, feel free to change it to `+`. – Lambda Fairy Nov 12 '13 at 00:06
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)

eg

>>> 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
John La Rooy
  • 295,403
  • 53
  • 369
  • 502
  • what is the difference between depth and calls here? shouldn't they be the same? – brain storm Nov 12 '13 at 00:21
  • @user1988876, the `depth` goes up and down as the function is entered and exited again. `calls` is just a count of how many times the function has been called. – John La Rooy Nov 12 '13 at 00:31